Hiểu bài toán

Bài toán yêu cầu tính tổng tất cả các ước số nguyên dương của một số nguyên dương n. Ví dụ, với n = 8, các ước là 1, 2, 4, 8, tổng là 15. Với n = 15, các ước là 1, 3, 5, 15, tổng là 24. Input gồm T test case, mỗi test case là một số n (1 ≤ n ≤ 10^6). Output là tổng các ước của n cho mỗi test case.

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

Cách Duyệt qua tất cả các số từ 1 đến n

for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
        sum += i;
    }
}

• Time Complexity: O(n) mỗi test case
• Space Complexity: O(1)

Phương pháp này kiểm tra từng số i từ 1 đến n. Nếu n chia hết cho i thì i là ước và cộng vào tổng. Với n tối đa 10^6 và T tối đa 10^3, thời gian chạy tối đa là 10^9 thao tác, quá chậm và sẽ bị TLE.

Cách Duyệt đến căn bậc hai (sqrt)

long long sum = 0;
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        sum += i;
        if (i != n / i) {
            sum += n / i;
        }
    }
}

• Time Complexity: O(sqrt(n)) mỗi test case
• Space Complexity: O(1)

Nếu i là ước của n thì n/i cũng là ước. Ta chỉ cần duyệt i từ 1 đến sqrt(n). Khi tìm được ước i, ta cộng i và n/i vào tổng. Phải kiểm tra i != n/i để tránh cộng hai lần đối với trường hợp n là số chính phương (ví dụ n=9, i=3). Với n tối đa 10^6, sqrt(n) ≈ 1000. Với T=1000, tổng thao tác khoảng 10^6, chạy rất nhanh.

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

Bài học kinh nghiệm

• Tính chất đối xứng của các ước: Nếu i là ước của n thì n/i cũng là ước. Điều này giúp giảm đáng kể số lần lặp từ O(n) xuống O(sqrt(n)).
• Đối với số chính phương, cần kiểm tra để không cộng trùng ước là căn bậc hai của nó.

Lỗi thường gặp

• Sử dụng biến tổng (sum) kiểu int có thể gây tràn số (overflow) vì tổng các ước có thể lớn hơn 2^31-1. Nên dùng kiểu long long.
• Quên kiểm tra điều kiện i != n/i dẫn đến cộng sai kết quả cho các số chính phương.
• Biến vòng lặp i kiểu int có thể tràn số khi nhân i*i nếu n quá lớn, nhưng với n ≤ 10^6 thì an toàn. Để an toàn tuyệt đối có thể dùng điều kiện i <= sqrt(n) hoặc kiểu long long.