C++ • Phân tích thuật toán

Tính tổng các ước thực sự của một số nguyên

Phân tích hàm tonguoc(x): tìm các cặp ước đến căn bậc hai, tránh cộng trùng khi số là số chính phương.

1. Bài toán

Cho số nguyên dương n. Tính tổng các ước dương của n, không tính chính n.

Ví dụ: Với n = 16, các ước thực sự là 1, 2, 4, 8. Vì vậy tổng S = 1 + 2 + 4 + 8 = 15.

2. Code C++ và chú thích

#include <iostream>
#define ll long long
using namespace std;

ll tonguoc(ll x)
{
    if (x <= 1) return 0; // Không có ước thực sự dương khi x = 1

    ll s = 1; // 1 luôn là ước của x (với x > 1)

    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0) // i là một ước của x
        {
            s += i + (x / i); // Cộng cả cặp ước

            if (i * i == x)
                s -= i; // Tránh cộng i hai lần nếu x là số chính phương
        }
    }
    return s;
}

int main()
{
    ll n;
    cin >> n;
    cout << tonguoc(n);
    return 0;
}
Lưu ý: Đây là phiên bản hoàn chỉnh có xử lý n ≤ 1. Với dữ liệu rất lớn, điều kiện i * i <= x có thể được thay bằng i <= x / i để tránh nguy cơ tràn số khi bình phương i.

3. Giải thích các lệnh quan trọng

Khởi tạo tổng

ll s = 1; — bắt đầu tổng bằng 1 vì 1 là ước của mọi số nguyên dương lớn hơn 1.

Vòng lặp đến căn bậc hai

for (ll i = 2; i * i <= x; i++) — nếu i là ước của x thì x/i cũng là ước. Vì vậy chỉ cần tìm một nửa các cặp ước, đến căn bậc hai của x.

Kiểm tra chia hết và cộng cặp ước

x % i == 0 kiểm tra x có chia hết cho i hay không. Nếu đúng, cộng cả i và x/i vào tổng.

Không cộng trùng số chính phương

Nếu i * i == x, hai ước trong cặp bằng nhau. Lệnh s -= i loại bỏ một lần cộng dư.

4. Mô phỏng với n = 16

iKiểm traXử lýTổng S
Khởi tạo—S = 11
216 % 2 = 0Cộng 2 + 811
316 % 3 ≠ 0Bỏ qua11
416 % 4 = 0Cộng 4 + 4, sau đó trừ 415
Kết quả: 15. Các ước thực sự: 1, 2, 4, 8.

5. Thử chương trình trực tiếp

Nhập một số nguyên dương từ 1 đến 1.000.000 để xem các ước thực sự và tổng.

Nhấn “Tính tổng ước” để xem kết quả.

6. Độ phức tạp thuật toán

O(√n)Thời gian — vòng lặp chỉ chạy đến căn bậc hai của n.
O(1)Bộ nhớ phụ — chỉ sử dụng một vài biến, không lưu danh sách ước.

So với cách duyệt từ 1 đến n − 1 (O(n)), cách làm này hiệu quả hơn đáng kể khi n lớn.

7. Câu hỏi củng cố

  1. Vì sao chỉ cần duyệt i đến căn bậc hai của n?
  2. Điều kiện n % i == 0 có ý nghĩa gì?
  3. Vì sao cần trừ i khi i * i == n?
  4. Nếu n = 25 thì các ước thực sự và tổng là bao nhiêu?
  5. Hãy sửa chương trình để tính số lượng ước thực sự thay vì tổng các ước.