Hiểu bài toán

Cho một số nguyên dương n. Yêu cầu tính tổng tất cả các ước số nguyên dương của n. Ví dụ, với n = 10, các ước là 1, 2, 5, 10, tổng là 18.

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

Cách Brute Force (Duyệt tất cả các số)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long sum = 0;
    for (long long i = 1; i <= n; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    cout << sum;
    return 0;
}

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

Phương pháp này duyệt qua tất cả các số từ 1 đến n. Với mỗi số i, nó kiểm tra xem i có chia hết cho n hay không. Nếu có, nó cộng i vào tổng. Phương pháp này đơn giản để hiểu nhưng quá chậm cho n lớn (ví dụ n = 10^9), vì nó thực hiện đến 10^9 lần lặp.

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

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

int main() {
    ll n, s = 0;
    cin >> n;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            s += i;
            ll j = n / i;
            if (i != j) {
                s += j;
            }
        }
    }
    cout << s;
    return 0;
}

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

Đây là phương pháp tối ưu được sử dụng trong các bài nộp. ước số luôn đến theo cặp (i, n/i). Nếu i là một ước số, thì n/i cũng là một ước số. Thay vì duyệt đến n, ta chỉ cần duyệt đến sqrt(n) (căn bậc hai của n). Nếu i chia hết cho n, ta cộng dồn i và n/i (trừ trường hợp i*i = n để tránh cộng trùng). Ví dụ n=100, duyệt i=1 -> cộng 1 và 100, i=2 -> cộng 2 và 50, ..., i=10 -> cộng 10 (vì 10 = 100/10). Độ phức tạp giảm từ O(n) xuống O(sqrt(n)), giúp giải quyết n lớn lên tới 10^9 rất nhanh.

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

Bài học kinh nghiệm

• Ước số xuất hiện theo cặp (i, n/i).
• Chỉ cần duyệt đến căn bậc hai của n (sqrt(n)) để tìm tất cả các cặp ước số này.
• Phải kiểm tra điều kiện 'i != j' (hoặc i*i != n) để tránh cộng hai lần ước số là chính nó (ví dụ n=100, i=10).

Lỗi thường gặp

• Sử dụng biến kiểu int導致 overflow khi n lớn (nên dùng long long).
• Sử dụng hàm sqrt(n) trong điều kiện lặp có thể gây sai số số thực, nên dùng điều kiện i * i <= n.
• Quên kiểm tra điều kiện i != j dẫn đến tính sai tổng với các số chính phương.