Hướng dẫn giải của SANGNT11: Số nguyên tố ghép
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
Dãy B được tạo bằng cách ghép hai số nguyên tố liên tiếp trong dãy A (2, 3, 5, 7, 11, ...): (2,3)→23, (5,7)→57, (11,13)→1113,... Trong B, các số nguyên tố xếp theo thứ tự xuất hiện, ta cần tìm số nguyên tố thứ K của dãy B (K <= 500). Đề dùng file SANGNT11.INP và SANGNT11.OUT.
Sub 1: Thử chia từng số ghép — ~O(K \cdot \sqrt{B})~, dùng khi ~K \le 30~
Sinh các số nguyên tố, ghép từng cặp liên tiếp và kiểm tra nguyên tố bằng thử chia, đếm tới khi đủ K.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng + Miller-Rabin — ~O(\text{LIM} + \text{số cặp} \cdot \log^3)~
Sàng các số nguyên tố đến một giới hạn đủ lớn (4·10^6). Với K lớn, số ghép có thể lên đến 10^13 nên thử chia chậm; dùng kiểm tra Miller-Rabin với bộ cơ sở xác định cho số 64-bit. Bẫy: phép nhân modulo cần __int128 để không tràn.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc K từ SANGNT11.INP. Nếu K <= 30 gọi sub1, ngược lại gọi sub2. Kết quả ghi ra SANGNT11.OUT.
#include <bits/stdc++.h>
using namespace std;
int K;
// Sub 1: chia thu tung so ghep — dung khi K <= 30 (so ghep nho)
bool isPrimeTrial(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
void sub1() {
vector<long long> pr; // danh sach so nguyen to A
for (long long x = 2; (int)pr.size() < 100000; x++)
if (isPrimeTrial(x)) pr.push_back(x);
int found = 0;
for (size_t i = 0; i + 1 < pr.size() && found < K; i += 2) {
long long a = pr[i], b = pr[i + 1];
long long p10 = 10;
while (p10 <= b) p10 *= 10;
long long ghep = a * p10 + b; // ghep a va b thanh mot so
if (isPrimeTrial(ghep)) {
found++;
if (found == K) cout << ghep << "\n";
}
}
}
// Kiem tra nguyen to cho so lon bang Miller-Rabin (bo co so xac dinh cho 64-bit)
long long mulmod(long long a, long long b, long long m) {
return (long long)((__int128)a * b % m);
}
long long powmod(long long a, long long e, long long m) {
long long r = 1;
a %= m;
while (e > 0) {
if (e & 1) r = mulmod(r, a, m);
a = mulmod(a, a, m);
e >>= 1;
}
return r;
}
bool isPrimeMR(long long n) {
if (n < 2) return false;
for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n % p == 0) return n == p;
}
long long d = n - 1;
int s = 0;
while (d % 2 == 0) { d /= 2; s++; }
for (long long a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
long long x = powmod(a, d, n);
if (x == 1 || x == n - 1) continue;
bool ok = false;
for (int r = 1; r < s; r++) {
x = mulmod(x, x, n);
if (x == n - 1) { ok = true; break; }
}
if (!ok) return false;
}
return true;
}
// Sub 2: sang lay cac so nguyen to, ghep cap lien tiep, kiem tra bang Miller-Rabin
void sub2() {
const int LIM = 4000000;
vector<bool> comp(LIM + 1, false);
vector<long long> pr;
for (long long i = 2; i <= LIM; i++) {
if (comp[i]) continue;
pr.push_back(i);
for (long long j = i * i; j <= LIM; j += i) comp[j] = true;
}
int found = 0;
for (size_t i = 0; i + 1 < pr.size() && found < K; i += 2) {
long long a = pr[i], b = pr[i + 1];
long long p10 = 10;
while (p10 <= b) p10 *= 10;
long long ghep = a * p10 + b;
if (isPrimeMR(ghep)) {
found++;
if (found == K) cout << ghep << "\n";
}
}
}
int main() {
freopen("SANGNT11.INP", "r", stdin);
freopen("SANGNT11.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> K;
if (K <= 30) sub1();
else sub2();
return 0;
}
Bình luận