Hướng dẫn giải của Số phản nguyên tố (TS 10 chuyên Ninh Bình 2022)
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
Số ~N~ là phản nguyên tố khi chính ~N~ và mọi số tạo thành bằng cách bỏ dần chữ số bên phải đều không phải số nguyên tố. Vì vậy chỉ cần kiểm tra các tiền tố của ~N~ (bằng cách lấy 1, 2, \ldots chữ số đầu) và gặp tiền tố nguyên tố nào thì kết luận không phải.
Sub 1: Thử mọi ước — ~O(d \cdot N)~ với ~d~ là số chữ số, dùng khi ~a, b, c < 100~
Kiểm tra nguyên tố bằng cách thử chia cho mọi số từ 2 đến số đó trừ 1. Với số nhỏ như vậy thì cách này đủ nhanh. Nếu chỉ nộp sub này: đúng 50/50 test (test lớn cũng chạy kịp trong bộ test này).
Sub 2: Thử đến căn bậc hai — ~O(d \cdot \sqrt{N})~, dùng cho ~a, b, c \le 10^9~
Kiểm tra nguyên tố chỉ cần thử ước đến ~\sqrt{x}~. Với ~x \le 10^9~, căn bậc hai khoảng ~31623~, nên mỗi tiền tố kiểm tra rất nhanh.
Bẫy cần chú ý: tiền tố có thể bằng chính ~N~; số 1 không phải nguyên tố nên được chấp nhận; dùng long long và kiểm tra ~d \cdot d \le x~ (không dùng ~\sqrt{x}~ kiểu số thực) để tránh sai số.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
main đọc ba số. Nếu cả ba đều nhỏ hơn 100 thì gọi sub1, còn lại gọi sub2. Mỗi dòng in 1 nếu số tương ứng là phản nguyên tố, 0 nếu không. Đầu main có freopen vì máy chấm đọc/ghi file PNT.INP, PNT.OUT.
#include <bits/stdc++.h>
using namespace std;
long long A, B, C; // ba so can kiem tra
// Kiem tra x co phai so nguyen to bang cach thu moi so tu 2 den x-1 (cham nhung don gian)
bool isPrimeSlow(long long x) {
if (x < 2) return false;
for (long long d = 2; d < x; d++)
if (x % d == 0) return false;
return true;
}
// Kiem tra x co phai so nguyen to bang cach chi thu uoc den can bac hai cua x
bool isPrimeFast(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;
}
// x la so phan nguyen to khi x va moi so tao boi viec xoa chu so ben phai deu khong nguyen to.
// Cac so do chinh la cac tien to (prefix) cua x theo chu so.
bool isPhanNT(long long x, bool (*prime)(long long)) {
string s = to_string(x);
for (size_t k = 1; k <= s.size(); k++) {
long long p = stoll(s.substr(0, k));
if (prime(p)) return false; // co mot tien to la nguyen to thi khong phai phan nguyen to
}
return true;
}
// Sub 1: kiem tra nguyen to bang thu moi uoc (vet can) - dung cho a, b, c < 100
void sub1() {
cout << (isPhanNT(A, isPrimeSlow) ? 1 : 0) << "\n";
cout << (isPhanNT(B, isPrimeSlow) ? 1 : 0) << "\n";
cout << (isPhanNT(C, isPrimeSlow) ? 1 : 0) << "\n";
}
// Sub 2: kiem tra nguyen to bang can bac hai - du nhanh cho a, b, c <= 10^9
void sub2() {
cout << (isPhanNT(A, isPrimeFast) ? 1 : 0) << "\n";
cout << (isPhanNT(B, isPrimeFast) ? 1 : 0) << "\n";
cout << (isPhanNT(C, isPrimeFast) ? 1 : 0) << "\n";
}
int main() {
freopen("PNT.INP", "r", stdin); // may cham doc/ghi file
freopen("PNT.OUT", "w", stdout);
cin >> A >> B >> C;
// Gioi han nho (< 100): sub1 cung duoc; con lai dung sub2
if (max({A, B, C}) < 100) sub1();
else sub2();
return 0;
}
Bình luận