Bài toán: Cho số nguyên dương n (n <= 109). Hãy tính tổng các ước nguyên dương của n?
Ví dụ: n = 12 thì tổng các ước nguyên dương sẽ là: 1 + 2 + 3 + 4 + 6 + 12 = 28
Với bài toán này, thông thường chúng ta sẽ code như sau:
#include <iostream>
using namespace std;
int main() {
freopen("SDIV.INP","r",stdin);
freopen("SDIV.OUT","w",stdout);
long n; int64_t t = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
if (n % i == 0) t += i;
}
cout << t;
return 0;
}
Tuy nhiên, thuật toán trên không tối ưu cho các số nguyên lớn. Tốc độ sẽ chậm và nếu bạn tham dự kỳ thi học sinh giỏi chấm trên phần mềm Themis sẽ không vượt quá 50% số điểm.
Chính vì vậy. Chúng ta xử lý bằng thuật toán theo phần code dưới đây:
#include <iostream>
#include <cmath>
using namespace std;
int main() {
freopen("SDIV.INP","r",stdin);
freopen("SDIV.OUT","w",stdout);
long n; int64_t t = 0;
cin >> n;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
int j = n/i;
if (i == j) t += j;
else t += i + j;
}
}
cout << t;
return 0;
}