Hướng dẫn giải của F19: Nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Ta có ~b^2 - a^2 = (b-a)(b+a)~. Tích này là số nguyên tố khi và chỉ khi một thừa số bằng 1 và thừa số còn lại là số nguyên tố, tức ~b - a = 1~ và ~a + b~ nguyên tố.
Sub 1: Tính trực tiếp — ~O(\sqrt{b^2 - a^2})~, dùng khi ~b \le 100~
Tính ~x = b^2 - a^2~ rồi kiểm tra nguyên tố bằng chia thử. Vì ~b \le 100~ nên ~x \le 10^4~, rất nhanh. Nếu chỉ nộp sub này: đúng 18/20 test (2 test lớn bị quá giờ khi chạy riêng sub này).
Sub 2: Dùng công thức hiệu hai bình phương — ~O(\sqrt{a+b})~
Chỉ cần kiểm tra ~b - a = 1~ và ~a + b~ nguyên tố. Lưu ý nếu ~a = b~ thì hiệu bằng 0, không phải nguyên tố. Số ~a + b~ đến ~2 \cdot 10^{14}~ nên chia thử đến ~\sqrt{a+b}~ vẫn kịp với ~t \le 10~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~t~ cặp, nếu mọi ~b \le 100~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int t;
long long A[15], B[15];
// Kiem tra nguyen to bang chia thu
bool isPrimeTD(long long x) {
if (x < 2) return false;
if (x % 2 == 0) return x == 2;
for (long long d = 3; d * d <= x; d += 2)
if (x % d == 0) return false;
return true;
}
// Sub 1: b <= 100. Tinh truc tiep x = b^2 - a^2 roi kiem tra nguyen to.
void sub1() {
for (int i = 0; i < t; i++) {
long long x = B[i] * B[i] - A[i] * A[i];
cout << (isPrimeTD(x) ? "YES" : "NO") << "\n";
}
}
// Sub 2: b^2 - a^2 = (b - a)(b + a). Tich nay la so nguyen to khi va chi khi
// b - a = 1 va b + a la so nguyen to (neu hai thua so deu > 1 thi tich la hop so).
void sub2() {
for (int i = 0; i < t; i++) {
long long d = B[i] - A[i], s = A[i] + B[i];
bool ok = (d == 1) && isPrimeTD(s);
cout << (ok ? "YES" : "NO") << "\n";
}
}
int main() {
cin >> t;
long long mx = 0;
for (int i = 0; i < t; i++) {
cin >> A[i] >> B[i];
mx = max(mx, B[i]);
}
if (mx <= 100) sub1();
else sub2();
return 0;
}
Bình luận