Hướng dẫn giải của F17: Số nguyên tố vòng
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
Đếm số nguyên tố vòng (mọi phép quay vòng các chữ số đều là số nguyên tố) nhỏ hơn ~n~. Với ~n \le 10^6~ có thể sàng trước rồi kiểm tra từng phép quay.
Sub 1: Chia thử — ~O(n \sqrt{n})~, dùng khi ~n \le 10^4~
Với mỗi số ~x < n~ là nguyên tố, sinh các phép quay vòng của ~x~ rồi kiểm tra từng số bằng chia thử. Nếu chỉ nộp sub này: đúng 20/20 test (sub này chạy riêng đủ 20/20 test của đề).
Sub 2: Sàng Eratosthenes — ~O(n \log \log n)~, dùng khi ~n > 10^4~
Sàng các số đến ~10^6~ một lần, sau đó kiểm tra mỗi phép quay bằng tra mảng ~O(1)~. Mọi phép quay của số nhỏ hơn ~10^6~ vẫn nằm trong mảng sàng. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~n~, dữ liệu nhỏ (~n \le 10^4~) gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
long long n; // dem so nguyen to vong nho hon n
bool composite[MAXV + 1]; // dung cho sub2: composite[x] = true neu x khong phai nguyen to
// Kiem tra nguyen to bang chia thu (dung cho sub1)
bool isPrimeTD(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;
}
// Sub 1: vet can. Voi moi x < n: kiem tra x va moi phep quay vong deu la nguyen to (chia thu).
void sub1() {
long long cnt = 0;
for (long long x = 2; x < n; x++) {
if (!isPrimeTD(x)) continue;
string s = to_string(x);
bool ok = true;
for (size_t i = 0; i < s.size() && ok; i++) {
s = s.substr(1) + s[0]; // quay vong sang trai mot chu so
if (!isPrimeTD(stoll(s))) ok = false;
}
if (ok) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: sang Eratosthenes den 10^6, moi phep quay vong tra cuu O(1).
void sub2() {
composite[0] = composite[1] = true;
for (long long i = 2; i * i <= MAXV; i++)
if (!composite[i])
for (long long j = i * i; j <= MAXV; j += i) composite[j] = true;
long long cnt = 0;
for (long long x = 2; x < n; x++) {
if (composite[x]) continue;
string s = to_string(x);
bool ok = true;
for (size_t i = 0; i < s.size() && ok; i++) {
s = s.substr(1) + s[0];
if (composite[stoll(s)]) ok = false;
}
if (ok) cnt++;
}
cout << cnt << "\n";
}
int main() {
cin >> n;
if (n <= 10000) sub1(); // n nho: chia thu da du nhanh
else sub2();
return 0;
}
Bình luận