Hướng dẫn giải của Mật ong (đề Quảng Trị 2020-2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Tổng lượng mật của đàn ong trong một ngày là tổng ~A_i \cdot f(A_i)~ với ~f(X)~ là số ước dương của ~X~.
Sub 1: Đếm ước trực tiếp — ~O(N \sqrt{A})~, dùng khi ~N \le 1000~
Với mỗi con ong, đếm ước của ~A_i~ bằng cách thử ~i \le \sqrt{A_i}~, mỗi cặp ~(i, A_i/i)~ tính 2 ước (1 ước nếu là số chính phương).
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng số ước — ~O(M \log M)~, với ~M = \max A_i~
Sàng số ước của mọi số đến ~M~: với mỗi ~d~, cộng 1 vào ~dc[m]~ với mọi bội ~m~ của ~d~. Sau đó tra ngay ~dc[A_i]~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> A;
// So uoc duong cua x, thu moi uoc i <= sqrt(x)
long long numDiv(long long x) {
long long c = 0;
for (long long i = 1; i * i <= x; i++)
if (x % i == 0) c += (i * i == x) ? 1 : 2;
return c;
}
// Sub 1: vét cạn — với mỗi con ong, đếm số ước bằng cách thử i <= sqrt(X). O(N sqrt(maxA))
void sub1() {
long long total = 0;
for (long long x : A) total += x * numDiv(x);
cout << total << "\n";
}
// Sub 2: sàng số ước — dc[m] là số ước của m, tính cho mọi m đến maxA bằng cách cộng 1 cho bội của mỗi d.
// O(M log M), M = maxA
void sub2() {
long long M = 0;
for (long long x : A) M = max(M, x);
vector<int> dc(M + 1, 0);
for (long long d = 1; d <= M; d++)
for (long long m = d; m <= M; m += d) dc[m]++;
long long total = 0;
for (long long x : A) total += x * dc[x];
cout << total << "\n";
}
int main() {
freopen("MATONG.INP", "r", stdin);
freopen("MATONG.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
A.resize(N);
for (int i = 0; i < N; i++) cin >> A[i];
if (N <= 1000) sub1(); // dữ liệu nhỏ: đếm ước trực tiếp
else sub2();
return 0;
}
Bình luận