Hiểu bài toán

Cho số nguyên dương n (1 ≤ n ≤ 10^9). Hãy đếm số lượng chữ số thập phân của phân số 1/n. Nếu phân số có chu kỳ vô hạn (số thập phân lặp lại vô hạn) thì in ra 'NO'. Phân số 1/n có số thập phân hữu hạn khi và chỉ khi n chỉ chứa các thừa số nguyên tố là 2 và 5 (n là số dạng 2^a * 5^b).

Các cách tiếp cận

Cách Phân tích thừa số nguyên tố (Prime Factorization)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count2 = 0, count5 = 0;

    // Đếm số lần chia hết cho 2
    while (n % 2 == 0) {
        n /= 2;
        count2++;
    }

    // Đếm số lần chia hết cho 5
    while (n % 5 == 0) {
        n /= 5;
        count5++;
    }

    // Nếu sau khi loại bỏ 2 và 5, n còn lại khác 1 thì có vô hạn chữ số
    if (n != 1) {
        cout << "NO" << endl;
    } else {
        cout << max(count2, count5) << endl;
    }

    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Đây là phương pháp trực tiếp nhất dựa trên tính chất toán học. Phân số 1/n có dạng số thập phân hữu hạn nếu và chỉ khi n có dạng 2^a * 5^b.

1. Ta thực hiện chia n cho 2 liên tục cho đến khi không chia được nữa, đếm số lần chia (biến count2).
2. Tương tự, chia n cho 5 liên tục, đếm số lần chia (biến count5).
3. Nếu sau quá trình này, n == 1, nghĩa là n chỉ chứa thừa số 2 và 5. Số chữ số thập phân là max(a, b) = max(count2, count5).
4. Nếu n > 1, nghĩa là còn thừa số nguyên tố khác (ví dụ 3, 7, 11...), dẫn đến chu kỳ vô hạn, in ra 'NO'.

Cách Tối ưu hóa Logic (Xử lý n=1)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    if (!(cin >> n)) return 0;
    if (n == 1) { cout << 0; return 0; } // Xử lý trường hợp đặc biệt
    int a = 0, b = 0;
    while (n % 2 == 0) { a++; n /= 2; }
    while (n % 5 == 0) { b++; n /= 5; }
    if (n != 1) cout << "NO";
    else cout << max(a, b);
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Cách tiếp cận này tương tự như cách 1 nhưng có thêm một chút tối ưu hóa và xử lý trường hợp biên.

• Sử dụng long long để đảm bảo không tràn số (dù đề bài cho phép n lên tới 10^9, int vẫn đủ nhưng long long an toàn hơn).
• Thêm dòng if (n == 1) { cout << 0; return 0; }. Đây là một cách ngắn gọn để xử lý ngay từ đầu: 1/1 = 1.0 (0 chữ số thập phân). Nếu không xử lý riêng, hàm max(a, b) sẽ trả về 0 (vì a=0, b=0), kết quả vẫn đúng nhưng xử lý rõ ràng hơn.
• Logic chính vẫn là loại bỏ các thừa số 2 và 5 rồi kiểm tra.

Cách Giải thuật chia để trị (Đếm số chữ số)

#include <iostream>
using namespace std;

int countDecimalDigits(int n) {
    int x = n, y = n;
    // Loại bỏ thừa số 2 và 5 khỏi n
    while (n % 2 == 0) n /= 2;
    while (n % 5 == 0) n /= 5;

    if (n == 1) {
        int count2 = 0, count5 = 0;
        while (x % 2 == 0) { x /= 2; count2++; }
        while (y % 5 == 0) { y /= 5; count5++; }
        return max(count2, count5);
    } else {
        return -1; // Đại diện cho vô hạn
    }
}

int main() {
    int n;
    cin >> n;
    int result = countDecimalDigits(n);
    if (result == -1) cout << "NO" << endl;
    else cout << result << endl;
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Đây là cách tách biệt logic thành hàm (function) để code dễ đọc và modular hơn.

• Hàm countDecimalDigits nhận n và trả về số chữ số. Nếu vô hạn, trả về -1.
• Trong hàm, ta thực hiện kiểm tra n có phải chỉ chứa 2 và 5 không (bằng cách copy n ra biến x, y hoặc dùng biến tạm).
• Nếu n == 1, ta đếm lại số lượng thừa số 2 (từ biến x cũ) và thừa số 5 (từ biến y cũ) để tính max.
• Hàm main chỉ việc gọi hàm và in kết quả tương ứng.
• Đây là cách viết code có cấu trúc hơn, thường thấy trong các bài toán lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Tính chất số học: 1/n có số thập phân hữu hạn iff n không chứa thừa số nguyên tố ngoài 2 và 5.
• Công thức độ dài: Nếu n = 2^a * 5^b, số chữ số thập phân của 1/n là max(a, b).
• Nếu n có thừa số nguyên tố khác (3, 7, 11...), phân số có chu kỳ vô hạn.

Lỗi thường gặp

• Quên xử lý trường hợp n = 1 (kết quả là 0).
• Sử dụng biến số nguyên nhỏ (int) cho n có thể gây tràn số nếu thực hiện nhân (trong các bài toán khác), ở đây chỉ chia nên int là đủ, nhưng long long là an toàn.
• Lầm tưởng rằng n không chia hết cho 2 và 5 là đủ điều kiện vô hạn. Sai, phải kiểm tra n có bằng 1 sau khi loại bỏ hết 2 và 5 không.