Hướng dẫn giải của [VTT Q4 Contest 08] Bài 2: Câu đố [QUIZ]
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
Đếm số ~x < n~ có đúng ~k~ ước. Với ~n \le 5 \times 10^6~ ta tính số ước của mọi số một lần bằng sàng.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 100~
Với mỗi ~x < n~, thử mọi ~i~ từ 1 đến ~x~ để đếm ước, so sánh với ~k~. Nếu chỉ nộp sub này: đúng 17/20 test (3 test lớn bị quá thời gian).
Sub 2: Sàng tuyến tính tính số ước — ~O(n)~
Sàng tuyến tính lưu ước nguyên tố nhỏ nhất ~lp[x]~ và số mũ ~ex[x]~ của nó trong ~x~. Khi tạo ~m = p \cdot i~ với ~p \le lp[i]~: nếu ~p = lp[i]~ thì số mũ của ~p~ tăng thêm 1, số ước đổi từ ~d[i]/(e+1) \cdot (e+2)~; nếu ~p < lp[i]~ thì ~p~ là thừa số mới với số mũ 1, số ước nhân đôi. Cuối cùng đếm các ~x < n~ có ~d[x] = k~. Lưu ý chỉ lấy ~x < n~ (không lấy ~n~). Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~n, k~; nếu ~n \le 100~ gọi sub1, ngược lại gọi sub2. 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.
#include <bits/stdc++.h>
using namespace std;
int n, k;
int dcnt[5000005], lp[5000005], ex[5000005]; // số ước, ước nguyên tố nhỏ nhất, số mũ của nó
vector<int> pr;
// Sub 1: với mỗi x < n, đếm ước bằng cách thử mọi i từ 1..x
void sub1() {
int res = 0;
for (int x = 1; x < n; x++) {
int c = 0;
for (int i = 1; i <= x; i++) if (x % i == 0) c++;
if (c == k) res++;
}
cout << res << "\n";
}
// Sub 2: sàng tuyến tính tính số ước của mọi số < n, O(n)
void sub2() {
dcnt[1] = 1;
for (int i = 2; i < n; i++) {
if (!lp[i]) { lp[i] = i; ex[i] = 1; dcnt[i] = 2; pr.push_back(i); }
for (int p : pr) {
long long m = (long long)p * i;
if (p > lp[i] || m >= n) break;
lp[m] = p;
if (p == lp[i]) { // p đã có trong i: tăng số mũ
ex[m] = ex[i] + 1;
dcnt[m] = dcnt[i] / (ex[i] + 1) * (ex[m] + 1);
} else { // p mới: nhân đôi theo p^1
ex[m] = 1;
dcnt[m] = dcnt[i] * 2;
}
}
}
int res = 0;
for (int x = 1; x < n; x++) if (dcnt[x] == k) res++;
cout << res << "\n";
}
int main() {
freopen("QUIZ.INP", "r", stdin);
freopen("QUIZ.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
if (n <= 100) sub1();
else sub2();
}
Bình luận