Hiểu bài toán

Cho N số nguyên dương a1, a2, ..., aN. Với mỗi số ai, cần tính số lượng ước số nguyên dương của nó. Ví dụ, nếu ai = 8, các ước là 1, 2, 4, 8 nên kết quả là 4. N ≤ 1000, ai ≤ 10^8.

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

Cách Brute Force (Duyệt ước)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        long long x;
        cin >> x;
        int cnt = 0;
        for (long long i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                if (i * i == x) cnt++;
                else cnt += 2;
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

• Time Complexity: O(N * sqrt(max(A)))
• Space Complexity: O(1)

Phương pháp này kiểm tra tất cả các số từ 1 đến căn bậc hai của ai. Nếu i là ước của ai thì i và ai/i đều là ước (trừ trường hợp i*i = ai). Với ai <= 10^8, sqrt(ai) <= 10^4. Với N=1000, tổng số thao tác khoảng 10^7, hoàn toàn chấp nhận được trong thời gian giới hạn.

Cách Phân tích thừa số nguyên tố

#include <iostream>
#include <cmath>
using namespace std;

int countDivisors(int a) {
    long long res = 1;
    for (int i = 2; i <= sqrt(a); i++) {
        if (a % i == 0) {
            int cnt = 0;
            while (a % i == 0) {
                a /= i;
                cnt++;
            }
            res *= (cnt + 1);
        }
    }
    if (a > 1) res *= 2;
    return res;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cout << countDivisors(a[i]) << "\n";
    return 0;
}

• Time Complexity: O(N * sqrt(max(A)))
• Space Complexity: O(1)

Số lượng ước của một số nếu biết phân tích n = p1^e1 * p2^e2 * ... * pk^ek là (e1+1)(e2+1)...*(ek+1). Ta duyệt các số i từ 2 đến sqrt(ai), nếu i là ước của ai thì đếm số mũ e của i và nhân (e+1) vào kết quả. Nếu sau vòng lặp ai còn > 1 thì ai là số nguyên tố với số mũ 1, nhân thêm 2. Độ phức tạp tương tự Brute Force nhưng có thể nhanh hơn một chút ở các số có nhiều ước.

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

Bài học kinh nghiệm

• Số lượng ước của số ai có thể tìm được bằng cách đếm cặp ước (i, ai/i) hoặc bằng công thức từ phân tích thừa số nguyên tố.
• Chỉ cần duyệt đến căn bậc hai của ai (sqrt(ai)) để tìm ước, giảm độ phức tạp đáng kể so với duyệt đến a_i.

Lỗi thường gặp

• Sử dụng biến kiểu int để lưu ai có thể bị tràn số nếu ai lên tới 10^8 và thực hiện phép nhân ii (i có thể lên tới 10^4, ii = 10^8, vẫn an toàn nhưng để chắc chắn nên dùng long long cho biến vòng lặp và kiểm tra điều kiện).
• Quên kiểm tra trường hợp ai là số chính phương (i*i == ai) để không đếm nhầm ước đó 2 lần.