Hướng dẫn giải của Bom chùm
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
Với mỗi số ~a_i~ cần tính tổng các ước ~\sigma(a_i)~ (số ước kể cả 1 và chính nó). Cách làm phụ thuộc vào độ lớn của ~a_i~ và ~q~.
Sub 1: Duyệt ước đến căn — ~O(q \sqrt{a})~, dùng khi ~q \le 10^4~, ~a \le 10^5~
Với mỗi ~a~, duyệt ~d~ từ 1 đến ~\sqrt{a}~; nếu ~d~ là ước thì cộng ~d~ và ~a/d~ (chú ý không cộng hai lần khi ~d = a/d~). Nếu chỉ nộp sub này: đúng 20/25 test.
Sub 2: Sàng tổng ước — ~O(M \log M)~, dùng khi ~a \le 10^6~
Với mỗi ~d~ từ 1 đến ~M = \max a~, cộng ~d~ vào mọi bội của ~d~. Sau đó trả lời mỗi số bằng tra bảng. Nếu chỉ nộp sub này: đúng 20/25 test (5 test lớn bị lỗi do ~a~ vượt ~10^6~).
Sub 3: Sàng đoạn cho ~a \le 10^{12}~
Các số ~a_i~ là ~q~ số liên tiếp nên ta sàng đoạn: với mỗi số nguyên tố ~p \le 10^6~ (vì ~\sqrt{10^{12}} = 10^6~), tìm các bội của ~p~ trong đoạn, tách hết lũy thừa ~p^e~ ra và nhân ~\sigma~ với ~1 + p + \dots + p^e~. Sau khi xử lý hết, phần còn dư (nếu lớn hơn 1) là một số nguyên tố ~r~, nhân thêm ~r + 1~. Với dữ liệu không liên tiếp, sub này phân tích từng số bằng các số nguyên tố. Tổng ước vẫn vừa trong long long. Nếu chỉ nộp sub này: đúng 25/25 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file BOMCHUM.INP/BOMCHUM.OUT); nếu ~q \le 10^4~ và ~a \le 10^5~ gọi sub1, nếu ~a \le 10^6~ gọi sub2, ngược lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Kết quả: 25/25 test.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
vector<ll> a;
// Sub 1: với mỗi số, duyệt ước đến căn — O(q * sqrt(a)), dùng khi q <= 10^4, a <= 10^5
void sub1() {
for (int i = 0; i < q; i++) {
ll n = a[i], s = 0;
for (ll d = 1; d * d <= n; d++)
if (n % d == 0) {
s += d;
if (d != n / d) s += n / d;
}
cout << s << (i + 1 < q ? ' ' : '\n');
}
}
// Sub 2: sàng tính tổng ước của mọi số đến max(a) — O(M log M), dùng khi a <= 10^6
void sub2() {
ll M = *max_element(a.begin(), a.end());
vector<ll> sig(M + 1, 0);
for (ll d = 1; d <= M; d++)
for (ll m = d; m <= M; m += d) sig[m] += d;
for (int i = 0; i < q; i++) cout << sig[a[i]] << (i + 1 < q ? ' ' : '\n');
}
// Sub 3: a lớn (đến 10^12) nhưng q số liên tiếp: sàng đoạn.
// Với mỗi số nguyên tố p <= 10^6, tách lũy thừa p khỏi các số trong đoạn; phần dư > 1 là một số nguyên tố.
void sub3() {
ll lo = a[0];
const int P = 1000100;
vector<char> comp(P + 1, 0);
vector<int> primes;
for (int i = 2; i <= P; i++) {
if (!comp[i]) { primes.push_back(i); for (ll j = (ll)i * i; j <= P; j += i) comp[j] = 1; }
}
bool consecutive = true;
for (int i = 0; i < q; i++) if (a[i] != lo + i) consecutive = false;
if (!consecutive) { // dữ liệu bất kỳ: phân tích từng số bằng các số nguyên tố
for (int i = 0; i < q; i++) {
ll n = a[i], s = 1;
for (int p : primes) {
if ((ll)p * p > n) break;
if (n % p == 0) {
ll term = 1, pw = 1;
while (n % p == 0) { n /= p; pw *= p; term += pw; }
s *= term;
}
}
if (n > 1) s *= n + 1;
cout << s << (i + 1 < q ? ' ' : '\n');
}
return;
}
vector<ll> rem(q), sig(q, 1);
for (int i = 0; i < q; i++) rem[i] = lo + i;
ll hi = lo + q - 1;
for (int p : primes) {
if ((ll)p * p > hi) break;
ll first = (lo + p - 1) / p * p;
for (ll m = first; m <= hi; m += p) {
int i = m - lo;
ll term = 1, pw = 1;
while (rem[i] % p == 0) { rem[i] /= p; pw *= p; term += pw; }
sig[i] *= term;
}
}
for (int i = 0; i < q; i++) {
if (rem[i] > 1) sig[i] *= rem[i] + 1;
cout << sig[i] << (i + 1 < q ? ' ' : '\n');
}
}
int main() {
freopen("BOMCHUM.INP", "r", stdin);
freopen("BOMCHUM.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> q;
a.resize(q);
for (auto& x : a) cin >> x;
ll mx = *max_element(a.begin(), a.end());
if (q <= 10000 && mx <= 100000) sub1();
else if (mx <= 1000000) sub2();
else sub3();
return 0;
}
Bình luận