Hướng dẫn giải của [VTT Q4 Contest 05] Bài 2: Số nguyên tố kép [PRIME]
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 tích lớn nhất của hai số nguyên tố phân biệt mà không vượt quá ~n~. Vì ~t~ lớn và ~n \le 10^6~, ta nên tính trước đáp án cho mọi ~n~.
Sub 1: Vét cạn mọi cặp — dùng khi ~t \le 1000, n \le 5000~
Sàng các số nguyên tố đến 5000, với mỗi câu hỏi thử mọi cặp ~(p, q)~ với ~p < q~, tích ~p \cdot q \le n~ và lấy tích lớn nhất. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Duyệt ngược từ ~n~ — dùng khi ~t = 1~
Với một câu hỏi, đi từ ~m = n~ xuống, phân tích ~m~ bằng chia thử đến căn; gặp số có đúng hai ước nguyên tố khác nhau, mỗi ước mũ 1 thì dừng. Số nguyên tố kép dày nên không phải lùi nhiều. Nếu chỉ nộp sub này: đúng 20/20 test (vẫn chạy kịp vì các test lớn ít câu hỏi).
Sub 3: Sàng và mảng max tiền tố — ~O(N \log \log N + t)~
Sàng ước nguyên tố nhỏ nhất ~spf~ đến ~10^6~. Với mỗi ~m~, đặt ~p = spf[m]~ và ~r = m / p~; ~m~ là số nguyên tố kép khi ~r~ là số nguyên tố và ~r \ne p~. Gọi ~best[m]~ là số nguyên tố kép lớn nhất không vượt quá ~m~, tính dần từ ~best[m-1]~. Mỗi câu hỏi trả lời ngay bằng ~best[n]~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc hết các câu hỏi; nếu ~t \le 1000~ và mọi ~n \le 5000~ 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;
const int MAXN = 1000005;
int t;
int q[100005];
int spf[MAXN], best[MAXN];
// Sub 1: sàng đến n rồi thử mọi cặp (p, q) nguyên tố, p < q, p*q <= n — dùng khi n <= 5000
void sub1() {
const int N = 5000;
vector<int> pr;
vector<bool> comp(N + 1, false);
for (int i = 2; i <= N; i++) {
if (!comp[i]) {
pr.push_back(i);
for (int j = 2 * i; j <= N; j += i) comp[j] = true;
}
}
for (int i = 0; i < t; i++) {
int res = 0;
for (size_t x = 0; x < pr.size(); x++)
for (size_t y = x + 1; y < pr.size(); y++) {
long long m = (long long)pr[x] * pr[y];
if (m > q[i]) break;
res = max(res, (int)m);
}
cout << res << "\n";
}
}
// Sub 2: dành cho t = 1 (nhiều câu hỏi vẫn đúng nhưng chậm) — duyệt m từ n xuống, phân tích bằng chia thử
bool isDouble(int m) {
int cnt = 0;
for (int p = 2; (long long)p * p <= m; p++) {
if (m % p == 0) {
int e = 0;
while (m % p == 0) { m /= p; e++; }
if (e > 1) return false;
cnt++;
}
}
if (m > 1) cnt++;
return cnt == 2;
}
void sub2() {
for (int i = 0; i < t; i++) { // mỗi câu hỏi xử lý độc lập
int m = q[i];
while (!isDouble(m)) m--;
cout << m << "\n";
}
}
// Sub 3: sàng ước nguyên tố nhỏ nhất, đánh dấu mọi số nguyên tố kép, rồi lấy max tiền tố
void sub3() {
const int N = 1000000;
for (int i = 2; i <= N; i++)
if (!spf[i])
for (int j = i; j <= N; j += i)
if (!spf[j]) spf[j] = i;
for (int m = 1; m <= N; m++) {
best[m] = best[m - 1];
if (m < 6) continue;
int p = spf[m], r = m / p;
// m = p * r, r nguyên tố và r != p
if (r > 1 && spf[r] == r && r != p) best[m] = m;
}
for (int i = 0; i < t; i++) cout << best[q[i]] << "\n";
}
int main() {
freopen("PRIME.INP", "r", stdin);
freopen("PRIME.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> t;
int mx = 0;
for (int i = 0; i < t; i++) { cin >> q[i]; mx = max(mx, q[i]); }
if (t <= 1000 && mx <= 5000) sub1();
else if (t == 1) sub2();
else sub3();
}
Bình luận