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
| i | Kiểm tra | Xử lý | Tổng S |
|---|---|---|---|
| Khởi tạo | — | S = 1 | 1 |
| 2 | 16 % 2 = 0 | Cộng 2 + 8 | 11 |
| 3 | 16 % 3 ≠ 0 | Bỏ qua | 11 |
| 4 | 16 % 4 = 0 | Cộng 4 + 4, sau đó trừ 4 | 15 |
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ố
- Vì sao chỉ cần duyệt i đến căn bậc hai của n?
- Điều kiện
n % i == 0có ý nghĩa gì? - Vì sao cần trừ i khi
i * i == n? - Nếu n = 25 thì các ước thực sự và tổng là bao nhiêu?
- Hãy sửa chương trình để tính số lượng ước thực sự thay vì tổng các ước.