Hướng dẫn giải của [VTT Q4 Contest 04] Bài 2: Số k lớn nhất [KMAX]
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 ~n~, tìm ~k \le n~ có nhiều ước nguyên tố phân biệt nhất, nếu hòa thì lấy ~k~ lớn nhất. Cần chú ý ~n = 1~ cho đáp án 1 (số 1 có 0 ước nguyên tố).
Sub 1: Vét cạn — ~O(T \cdot n \sqrt{n})~, dùng khi ~T \le 100, n \le 500~
Với mỗi câu hỏi duyệt mọi ~k \le n~, đếm số ước nguyên tố bằng chia thử, cập nhật đáp án bằng điều kiện ">=" để khi hòa luôn lấy ~k~ lớn hơn. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Sàng đếm ước nguyên tố
Với mỗi số nguyên tố ~p~ (chưa bị đánh dấu), cộng 1 vào số ước nguyên tố của mọi bội của ~p~, tổng thời gian ~O(n \log \log n)~ cho một câu hỏi. Rất tốt khi chỉ có một câu hỏi (~T = 1~) nhưng nếu sàng lại cho từng câu thì ~T~ lớn sẽ quá giờ. Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 3: Sàng một lần cho mọi câu hỏi
Sàng một lần đến ~10^6~, rồi gọi ~best[k]~ là đáp án của ~n = k~: ~best[k] = k~ nếu số ước nguyên tố của ~k~ không nhỏ hơn của ~best[k-1]~, ngược lại ~best[k] = best[k-1]~. Mỗi câu hỏi trả lời trong ~O(1)~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc toàn bộ câu hỏi; nếu ~T \le 100~ và mọi ~n \le 500~ gọi sub1, nếu ~T = 1~ gọi sub2, còn 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.
#include <bits/stdc++.h>
using namespace std;
int t;
vector<int> q;
const int MX = 1000000;
int omega[MX + 5], best[MX + 5];
// Đếm số ước nguyên tố phân biệt của k bằng chia thử
int dem(int k) {
int c = 0;
for (int p = 2; (long long)p * p <= k; p++)
if (k % p == 0) {
c++;
while (k % p == 0) k /= p;
}
if (k > 1) c++;
return c;
}
// Sub 1: với mỗi câu hỏi duyệt mọi k ≤ n, đếm ước bằng chia thử (n ≤ 500, T ≤ 100)
void sub1() {
for (int n : q) {
int bc = -1, bk = 1;
for (int k = 1; k <= n; k++) {
int c = dem(k);
if (c >= bc) { bc = c; bk = k; } // >= để lấy k lớn nhất
}
cout << bk << "\n";
}
}
// Sub 2: với mỗi câu hỏi, sàng đếm ước nguyên tố cho các số ≤ n rồi duyệt một lần
// (nhanh khi chỉ có một câu hỏi, chậm khi nhiều câu)
void sub2() {
for (int n : q) {
vector<int> w(n + 1, 0);
for (int p = 2; p <= n; p++)
if (w[p] == 0) // p là số nguyên tố
for (int m = p; m <= n; m += p) w[m]++;
int bc = -1, bk = 1;
for (int k = 1; k <= n; k++)
if (w[k] >= bc) { bc = w[k]; bk = k; }
cout << bk << "\n";
}
}
// Sub 3: sàng một lần đến 10^6, best[n] = đáp án cho n, trả lời mỗi câu hỏi O(1)
void sub3() {
for (int p = 2; p <= MX; p++)
if (omega[p] == 0)
for (int m = p; m <= MX; m += p) omega[m]++;
best[1] = 1;
for (int k = 2; k <= MX; k++)
best[k] = (omega[k] >= omega[best[k - 1]]) ? k : best[k - 1];
for (int n : q) cout << best[n] << "\n";
}
int main() {
freopen("KMAX.INP", "r", stdin);
freopen("KMAX.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> t;
q.resize(t);
int mx = 0;
for (int &x : q) { cin >> x; mx = max(mx, x); }
if (t <= 100 && mx <= 500) sub1();
else if (t == 1) sub2();
else sub3();
}
Bình luận