Hướng dẫn giải của [200 đề thầy Đức] Bài 48: Bộ ba số nguyên tố
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ìm mọi bộ ba số nguyên tố ~x < y < z \le N~ thỏa mãn ~x^2 + y^2 = z~, in theo thứ tự tăng dần, hoặc in -1 nếu không có.
Sub 1: Vét cạn — ~O(N^3 \sqrt{N})~, dùng khi ~N \le 100~
Thử mọi bộ ba ~x < y < z \le N~, kiểm tra điều kiện và cả ba số nguyên tố bằng thử chia.
Nếu chỉ nộp sub này: đúng 4/9 test (các test còn lại quá chậm).
Sub 2: Sàng và duyệt cặp — ~O(N^2)~ trên các cặp nguyên tố, dùng khi ~N \le 5000~
Sàng nguyên tố đến ~N~. Duyệt cặp nguyên tố ~x < y~ với ~x^2 + y^2 \le N~ và kiểm tra ~z = x^2 + y^2~ có nguyên tố nhờ bảng sàng.
Nếu chỉ nộp sub này: đúng 7/9 test.
Sub 3: Chẵn lẻ — ~O(\sqrt{N} \cdot \sqrt{N} / \ln N)~, dùng cho ~N \le 10^9~
Nếu ~z~ là số nguyên tố lẻ thì trong ~x, y~ phải có đúng một số chẵn, và số nguyên tố chẵn duy nhất là 2. Vì ~x < y~ nên ~x = 2~, khi đó ~z = y^2 + 4~. Chỉ cần duyệt ~y~ nguyên tố lẻ và kiểm tra ~z~ bằng các số nguyên tố đến ~\sqrt{N}~.
Nếu chỉ nộp sub này: đúng 9/9 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;
long long N;
bool isPrimeTrial(long long x) {
if (x < 2) return false;
for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
}
// Sub 1: vét cạn — thử mọi bộ x < y < z <= N, kiểm tra x^2 + y^2 = z và cả ba đều nguyên tố. O(N^3 sqrt N)
void sub1() {
bool found = false;
for (long long x = 2; x <= N; x++)
for (long long y = x + 1; y <= N; y++)
for (long long z = y + 1; z <= N; z++)
if (x * x + y * y == z && isPrimeTrial(x) && isPrimeTrial(y) && isPrimeTrial(z)) {
cout << x << " " << y << " " << z << "\n";
found = true;
}
if (!found) cout << -1 << "\n";
}
// Sub 2: sàng nguyên tố đến N. Thử mọi cặp nguyên tố x < y với z = x^2 + y^2 <= N,
// kiểm tra z nguyên tố nhờ bảng sàng. Dùng khi N <= 5000
void sub2() {
vector<char> comp(N + 1, 0);
comp[0] = comp[1] = 1;
for (long long i = 2; i <= N; i++) {
if (comp[i]) continue;
for (long long j = i * i; j <= N; j += i) comp[j] = 1;
}
bool found = false;
for (long long x = 2; x <= N; x++) {
if (comp[x]) continue;
for (long long y = x + 1; x * x + y * y <= N; y++) {
if (comp[y]) continue;
long long z = x * x + y * y;
if (!comp[z]) { cout << x << " " << y << " " << z << "\n"; found = true; }
}
}
if (!found) cout << -1 << "\n";
}
// Sub 3: chẵn lẻ — z = x^2 + y^2 là số nguyên tố. Nếu z lẻ thì trong x, y có đúng một số chẵn,
// mà số nguyên tố chẵn duy nhất là 2, và x < y nên x = 2. Khi đó z = y^2 + 4, chỉ cần duyệt
// y nguyên tố lẻ và thử chia z với các số nguyên tố đến sqrt(N). Dùng cho N lớn (đến 10^9)
void sub3() {
long long lim = 1;
while (lim * lim <= N) lim++; // lim >= sqrt(N)
vector<char> comp(lim + 1, 0);
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] = 1;
}
auto isP = [&](long long v) -> bool {
if (v < 2) return false;
for (long long p : pr) {
if (p * p > v) break;
if (v % p == 0) return false;
}
return true;
};
bool found = false;
for (long long y : pr) {
if (y == 2) continue; // cần y > x = 2
long long z = y * y + 4;
if (z > N) break;
if (isP(z)) { cout << 2 << " " << y << " " << z << "\n"; found = true; }
}
if (!found) cout << -1 << "\n";
}
int main() {
cin >> N;
if (N <= 100) sub1(); // dữ liệu nhỏ: vét cạn
else if (N <= 5000) sub2(); // sàng nguyên tố
else sub3(); // N lớn: dùng tính chất chẵn lẻ
return 0;
}
Bình luận