Hướng dẫn giải của [200 đề thầy Đức] Bài 92: Tổng ước
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần tính tổng của $\sigma(d)$ với $d$ chạy qua mọi ước của $n$, trong đó $\sigma(d)$ là tổng các ước của $d$. Ví dụ $n = 10$: các ước là $1, 2, 5, 10$ có tổng ước lần lượt là $1, 3, 6, 18$, cộng lại được $28$.
Sub 1: Vét cạn — ~O(n + \sigma(n))~, dùng khi ~n \le 10^4~
Với mỗi ước $d$ của $n$, thử từng số $e$ từ $1$ đến $d$ và cộng $e$ khi $e \mid d$. Đúng với mọi $n$ trong đề.
Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Công thức nhân tính — ~O(\sqrt{n})~
Hàm $f(n) = \sum{d \mid n} \sigma(d)$ là hàm nhân, nên $f(n) = \prod{p^e \| n} f(p^e)$ với
$$f(p^e) = \sum_{i=0}^{e} \sigma(p^i), \quad \sigma(p^i) = 1 + p + \dots + p^i$$
Ví dụ $n = 54 = 2 \cdot 3^3$: $f(2) = 1 + 3 = 4$, $f(3^3) = 1 + 4 + 13 + 40 = 58$, nên $f(54) = 4 \cdot 58 = 232$, khớp với đề.
Bẫy cần chú ý: nếu sau khi chia hết các thừa số nhỏ còn lại một số $> 1$ thì đó là một thừa số nguyên tố mũ $1$, có $f(p) = 2 + p$.
Chương trình hoàn chỉnh
Chương trình đọc $T$ bộ dữ liệu. Nếu mọi $n \le 10^4$ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int T;
vector<long long> ns; // các bộ dữ liệu n
// Sub 1: vét cạn — liệt kê các ước d của n; với mỗi d, tính tổng các ước của d bằng cách thử
// từng số e từ 1 đến d. Dùng khi n <= 10^4 (đề bài).
void sub1() {
for (int t = 0; t < T; t++) {
long long n = ns[t], total = 0;
for (long long d = 1; d <= n; d++) {
if (n % d != 0) continue; // d là ước của n
for (long long e = 1; e <= d; e++)
if (d % e == 0) total += e; // e là ước của d: cộng vào tổng σ(d)
}
cout << total << "\n";
}
}
// Sub 2: công thức nhân tính. Hàm f(n) = tổng σ(d) với d | n là hàm nhân,
// nên f(n) = Π f(p^e) với f(p^e) = Σ_{i=0}^{e} σ(p^i), σ(p^i) = 1 + p + ... + p^i.
// Phân tích thừa số nguyên tố bằng thử chia đến căn n.
void sub2() {
for (int t = 0; t < T; t++) {
long long n = ns[t], res = 1;
for (long long p = 2; p * p <= n; p++) {
if (n % p) continue;
int e = 0;
while (n % p == 0) { n /= p; e++; }
long long sumSigma = 0, sig = 1, pw = 1; // sig = σ(p^i), pw = p^i
for (int i = 0; i <= e; i++) {
sumSigma += sig;
pw *= p;
sig += pw;
}
res *= sumSigma;
}
if (n > 1) res *= (2 + n); // còn một thừa số nguyên tố p mũ 1: f(p) = 2 + p
cout << res << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
ns.resize(T);
bool small = true;
for (int t = 0; t < T; t++) {
cin >> ns[t];
if (ns[t] > 10000) small = false;
}
if (small) sub1(); // n nhỏ: vét cạn
else sub2(); // n lớn: công thức
return 0;
}
Bình luận