Hướng dẫn giải của Số nguyên tố (PRIME) (Đề HSG 12 Phú Thọ 2022-2023)
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
Từ ~N~ ta được ~M~ bằng cách giữ hoặc xóa các chữ số của ~N~. Tìm số nguyên tố lớn nhất trong ~M~, hoặc in -1 nếu không có. Số chữ số của ~N~ không quá 10 nên có tối đa 1023 cách chọn khác rỗng.
Sub 1: Thử chia trực tiếp — ~O(2^{len} \sqrt{N})~, dùng khi ~N \le 10^6~
Duyệt mọi tập con khác rỗng các chữ số, ghép thành số, kiểm tra nguyên tố bằng cách thử chia đến căn.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Dùng bảng số nguyên tố — ~O(2^{len} \cdot \sqrt{N} / \ln N)~, dùng khi ~N \le 10^9~
Cùng cách duyệt tập con, nhưng chỉ thử chia với các số nguyên tố đến ~31623~ lấy từ một bảng sàng.
Nếu chỉ nộp sub này: đúng 20/20 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;
string s; // các chữ số của 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;
}
// Duyệt mọi cách giữ một tập con khác rỗng các chữ số của N (không đổi thứ tự),
// trả về số nguyên tố lớn nhất trong các số tạo được, hoặc -1 nếu không có.
long long solveWith(bool (*isP)(long long)) {
int len = s.size();
long long best = -1;
for (int mask = 1; mask < (1 << len); mask++) {
long long v = 0;
for (int i = 0; i < len; i++)
if (mask >> i & 1) v = v * 10 + (s[i] - '0');
if (v > best && isP(v)) best = v;
}
return best;
}
// Sub 1: vét cạn — mỗi số tạo được thử chia bằng mọi số đến sqrt. N <= 10^6
void sub1() {
cout << solveWith(isPrimeTrial) << "\n";
}
// Sub 2: sàng các số nguyên tố đến 31623 một lần, rồi chỉ thử chia với các số nguyên tố đó. N <= 10^9
void sub2() {
const int LIM = 31623;
vector<char> comp(LIM + 1, 0);
vector<long long> primes;
for (int i = 2; i <= LIM; i++) {
if (comp[i]) continue;
primes.push_back(i);
for (long long j = (long long)i * i; j <= LIM; j += i) comp[j] = 1;
}
// kiểm tra nguyên tố nhờ bảng số nguyên tố (dùng trực tiếp trong lambda)
auto isP = [&](long long v) -> bool {
if (v < 2) return false;
for (long long p : primes) {
if (p * p > v) break;
if (v % p == 0) return v == p;
}
return true;
};
long long best = -1;
int len = s.size();
for (int mask = 1; mask < (1 << len); mask++) {
long long v = 0;
for (int i = 0; i < len; i++)
if (mask >> i & 1) v = v * 10 + (s[i] - '0');
if (v > best && isP(v)) best = v;
}
cout << best << "\n";
}
int main() {
freopen("PRIME.INP", "r", stdin);
freopen("PRIME.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> s;
long long N = stoll(s);
if (N <= 1000000) sub1(); // dữ liệu nhỏ: thử chia trực tiếp
else sub2();
return 0;
}
Bình luận