Số Nguyên Tố Hoàn Hảo
Đề bài
Tèo là một học sinh yêu thích số học, đặc biệt là với các số nguyên tố. Tèo phát hiện ra các số nguyên tố đặc biệt mà Tèo gọi là các “số nguyên tố hoàn hảo”. Theo định nghĩa của Tèo, $n$ là “số nguyên tố hoàn hảo” khi thỏa đồng thời các điều kiện sau:
- $n$ là số nguyên tố;
- $n$ là số đối xứng, nghĩa là khi đảo ngược các chữ số của $n$ ta được một số cũng chính là số $n$;
- $n$ có các chữ số đều là số nguyên tố.
Ví dụ: số $353$ là “số nguyên tố hoàn hảo” có 3 chữ số vì $353$ là số nguyên tố, $353$ là số đối xứng và cả ba chữ số $3, 5, 3$ của nó đều là số nguyên tố.
Yêu cầu: Hãy giúp Tèo tìm tất cả các “số nguyên tố hoàn hảo” có $n$ chữ số.
Input: Ghi một số nguyên dương $n$ $(1 \le n \le 12)$.
Output: Một dòng duy nhất ghi số lượng các “số nguyên tố hoàn hảo” tìm được.
14Giải thích: Các “số nguyên tố hoàn hảo” có một chữ số là: $2, 3, 5, 7$.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Vét cạnXét hết tất cả các số có N chữ số
Cách cơ bản nhất đó là vét cạn xét hết tất cả mọi trường hợp có thể có, nghĩa là xét hết tất cả các số có $N$ chữ số, rồi với mỗi số trong đó ta đi kiểm tra xem nó có thoả là số nguyên tố hoàn hảo không? Nếu số nào thoả thì tăng biến đếm lên. Sau cùng ta có biến đếm chính là kết quả bài toán.
Dễ dàng thấy cách này sẽ không ổn: chưa xét đến độ phức tạp của việc kiểm tra từng số, chỉ riêng việc đi qua tất cả các số đó thôi đã rất lớn rồi. Với số có $N$ chữ số thì ta phải xét phạm vi từ $10^{N-1}$ đến $10^N - 1$.
- Nếu $N \le 8$ thì còn có thể chạy được (cỡ $9 \cdot 10^7$ số là cùng).
- Nhưng từ $N = 9$ trở đi thì miền giá trị rất lớn. Ví dụ $N = 9$ thì phải xét từ $10^8$ (100 triệu) đến $10^9 - 1$ (999 triệu 999 ngàn 999), tức là $10^9 - 10^8 = 900$ triệu số. Trong khi ngưỡng giới hạn 1 giây thì vòng lặp chỉ chạy tối đa cỡ $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$ thôi là quá mức rồi. 900 triệu là vượt ngưỡng gấp cả 9 lần!
- Mới $N = 9$ đã vậy, với $N = 10, 11, 12$ thì còn khủng khiếp cỡ nào nữa.
Nên cách làm này cùng lắm nếu bạn nào không nhìn ra được cách làm tối ưu thì buộc làm cách này để vét được điểm nào hay điểm đó thôi. Source code cho cách làm vét cạn để các bạn tham khảo thấy rõ những gì mình phân tích:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
bool isPalind(long long x){
long long rever = 0;
long long temp = x;
while(temp){
rever = rever * 10 + temp % 10;
temp /= 10;
}
return rever == x;
}
bool isPerfectPrime(long long x){
if(!isPalind(x) || !isPrime(x)){
return false;
}
while(x){
if(!isPrime(x % 10)){
return false;
}
x /= 10;
}
return true;
}
int main(){
int n;
cin >> n;
long long start = (long long)pow(10.0, n - 1);
long long finish = (long long)pow(10.0, n) - 1;
long long cnt = 0;
for(long long i = start; i <= finish; ++i){
if(isPerfectPrime(i)){
cnt++;
}
}
cout << cnt;
return 0;
}def is_prime(x):
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return x >= 2
def is_palind(x):
return str(x) == str(x)[::-1]
def is_perfect_prime(x):
if not is_palind(x) or not is_prime(x):
return False
return all(is_prime(int(c)) for c in str(x))
n = int(input())
start = 10 ** (n - 1)
finish = 10 ** n - 1
cnt = 0
for i in range(start, finish + 1):
if is_perfect_prime(i):
cnt += 1
print(cnt)Trong code có 3 hàm nhỏ:
isPrime(x): thử chia $x$ cho các số $i$ từ 2 trong khi $i \cdot i \le x$; chia hết thì $x$ không nguyên tố. Cuối cùng phải có $x \ge 2$ (vì 0 và 1 không là số nguyên tố).isPalind(x): dựng số đảo ngượcreverbằng cách liên tục lấy chữ số cuốitemp % 10gắn vào saurever, rồi sorever == x.isPerfectPrime(x): phải đối xứng, phải nguyên tố, rồi tách từng chữ sốx % 10kiểm tra cũng phải nguyên tố.
Với $X$ là độ phức tạp của bước kiểm tra một số có phải số nguyên tố hoàn hảo không. Như đã phân tích thì cách này chắc chắn sẽ bị TLE với $N$ lớn. Tuy nhiên hãy vẫn nên cài đặt nó để sau này ta lấy nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu nhé.
Nhận xétChỉ có 4 chữ số được dùng: 2, 3, 5, 7
Giờ ta sẽ nói về cách làm tốt hơn. Trong các yếu tố để là số nguyên tố hoàn hảo thì có 2 yếu tố rất mạnh: chỉ bao gồm các chữ số là số nguyên tố và là số đối xứng. Chính 2 yếu tố này kết hợp lại sẽ giúp ta giảm thiểu được rất nhiều số phải xét không cần thiết, số lượng các số còn phải xét lúc này sẽ không bao nhiêu cả. Lúc này ta chỉ cần đi kiểm tra tính nguyên tố với những số đó thôi, rồi số nào thoả thì tăng biến đếm lên.
Tại sao lại ít? Vì trong các chữ số từ 0 đến 9 chỉ có đúng 4 chữ số 2, 3, 5, 7 là các chữ số nguyên tố. Từ 4 chữ số này ta dựng lên các số đối xứng có độ dài $N$:
- $N = 1$: $2, 3, 5, 7$ → tổng cộng có 4 số.
- $N = 2$: $22, 33, 55, 77$ → tổng cộng có 4 số.
- $N = 3$: gồm tất cả các trường hợp của $N = 1$, mỗi trường hợp được kẹp giữa bởi 2 đầu là lần lượt các chữ số 2, 3, 5, 7: $222, 232,$ $252,$ $272,$ $323,$ $333,$ $353,$ $373,$ $525,$ $535,$ $555,$ $575,$ $727,$ $737,$ $757,$ $777$ → tổng cộng có 16 số.
- $N = 4$: tương tự lấy các trường hợp của $N = 2$ kẹp giữa: $2222,$ $2332,$ $2552,$ $2772,$ $3223,$ $3333,$ $3553,$ $3773,$ $5225,$ $5335,$ $5555,$ $5775,$ $7227,$ $7337,$ $7557,$ $7777$ → 16 số.
- $N = 5$: lấy các trường hợp của $N = 3$ kẹp giữa: $22222,$ $22322,$ $22522,$ $22722,$ $32223,$ $32323,$ $\dots$
Như vậy nếu $N$ chẵn, giả sử $N = 10$, thì ta phải tính ra trường hợp $N = 2$, từ đó tính ra $N = 4$, $N = 6$, $N = 8$ rồi mới tới $N = 10$. Tương tự nếu $N$ lẻ, giả sử $N = 9$, thì đi từ $N = 1 \to 3 \to 5 \to 7 \to 9$. Bảng dưới so sánh số lượng phải xét của 2 cách:
| N | Vét cạn xét | Hàng đợi xét | Đáp án |
|---|---|---|---|
| 1 | 9 | 4 | 4 |
| 2 | 90 | 4 | 0 |
| 3 | 900 | 16 | 4 |
| 4 | 9.000 | 16 | 0 |
| 5 | 9·104 | 64 | 11 |
| 6 | 9·105 | 64 | 0 |
| 7 | 9·106 | 256 | 18 |
| 8 | 9·107 | 256 | 0 |
| 9 | 9·108 | 1024 | 77 |
| 10 | 9·109 | 1024 | 0 |
| 11 | 9·1010 | 4096 | 218 |
| 12 | 9·1011 | 4096 | 0 |
Trường hợp $N$ lớn nhất là 12 thì cả thảy chỉ có 4096 số cần xét, trong khi vét cạn phải xét $10^{12} - 10^{11} = 9 \cdot 10^{11}$, tức là 900 tỷ số. Các bạn đã thấy nó được rút ngắn lại kinh khủng chưa?
100%Sinh số bằng hàng đợi (khử đệ quy)
Vấn đề giờ chỉ là làm sao tạo ra đủ các số có độ dài $N$ chỉ gồm các chữ số 2, 3, 5, 7 và là số đối xứng. Nếu bạn nào vững kiến thức về đệ quy là có thể xử lý nhanh gọn, nhưng nếu bạn nào không biết hay không vững đệ quy thì ở đây mình sẽ chỉ cho các bạn cách xử lý không cần dùng đệ quy để dễ hình dung. Tuy nhiên nó đòi hỏi các bạn phải có kiến thức về cấu trúc dữ liệu hàng đợi (Queue) vì ta sẽ vận dụng nó để khử đệ quy. Bạn nào chưa biết có thể Google tìm hiểu thêm nhé, nó cũng rất đơn giản thôi không có gì phức tạp cả.
- Xét $N$ chẵn hay lẻ. Nếu lẻ thì khởi tạo hàng đợi chứa 4 chuỗi
"2","3","5","7"và $i = 1$. Nếu chẵn thì khởi tạo hàng đợi chứa"22","33","55","77"và $i = 2$. - Tại sao lại dùng kiểu chuỗi? Bởi chuỗi có thể nhanh chóng ghép được bằng phép toán
+hỗ trợ sẵn. Ví dụ cóstring x = "22"thì để tạo ra"2222"chỉ đơn giảny = "2" + x + "2". - Vòng lặp chạy cho đến khi $i$ bằng $N$, mỗi bước $i$ += 2. Cứ sinh ra các số của trường hợp $i = 1$, rồi từ đó sinh ra các số của trường hợp $i = 3$, rồi $i = 5$…
- Mỗi lần lặp: lấy lần lượt từng chuỗi $s$ ở đầu hàng đợi ra và đẩy 4 chuỗi mới vào cuối hàng đợi:
"2" + s + "2","3" + s + "3","5" + s + "5","7" + s + "7". - Cần lưu ý: nếu chuỗi $s$ ở đầu hàng đợi có độ dài bằng $N$ thì dừng ngay, vì giờ đây toàn bộ hàng đợi đều đang chứa các số có độ dài $N$ rồi, quy trình tạo số đã hoàn thành.
- Cuối cùng lấy từng số trong hàng đợi ra kiểm tra số nguyên tố cho đến khi hàng đợi rỗng, đếm số lượng số nguyên tố, đó chính là số các số nguyên tố hoàn hảo.
Chạy tay thử với N = 3
$N$ lẻ nên khởi tạo $i = 1$ và hàng đợi (từ đầu đến cuối) là: 2 3 5 7. Xét $i = 1$ khác $N = 3$ nên vào vòng lặp:
- Lấy
2ra (độ dài 1 khác 3) → sinh222 323 525 727. Hàng đợi:3 5 7 222 323 525 727. - Lấy
3ra → sinh232 333 535 737. Hàng đợi:5 7 222 323 525 727 232 333 535 737. - Lấy
5ra → sinh252 353 555 757. Hàng đợi:7 222 … 737 252 353 555 757. - Lấy
7ra → sinh272 373 575 777. Hàng đợi giờ chứa đúng 16 số có 3 chữ số. - Đầu hàng đợi là
222có độ dài 3 bằng $N$ → dừng quy trình sinh số.
Lúc này $i$ += 2 thành $i = 3$ bằng $N$ nên kết thúc. Chứ nếu giả sử $N = 5$ chẳng hạn thì ta phải tiếp tục thêm 1 tầng nữa nhé các bạn. Em nhập $N$ rồi bấm Tiếp để xem từng bước sinh số và kiểm tra nguyên tố:
Source code để các bạn tham khảo thấy rõ những gì mình phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; ++i){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
int n;
cin >> n;
queue<string> q;
int i;
if(n % 2 != 0){
q.push("2");
q.push("3");
q.push("5");
q.push("7");
i = 1;
}
else{
q.push("22");
q.push("33");
q.push("55");
q.push("77");
i = 2;
}
while(i != n){
while(!q.empty()){
string s = q.front();
if(s.length() == n){
break;
}
q.pop();
q.push("2" + s + "2");
q.push("3" + s + "3");
q.push("5" + s + "5");
q.push("7" + s + "7");
}
i += 2;
}
int cnt = 0;
while(!q.empty()){
if(isPrime(stoll(q.front()))){
cnt++;
}
q.pop();
}
cout << cnt;
return 0;
}from collections import deque
def is_prime(x):
# Miller-Rabin tất định: với x < 3.4 * 10^12 chỉ cần thử 6 cơ số này
if x < 2:
return False
for p in (2, 3, 5, 7, 11, 13):
if x % p == 0:
return x == p
d, s = x - 1, 0
while d % 2 == 0:
d //= 2
s += 1
for a in (2, 3, 5, 7, 11, 13):
y = pow(a, d, x)
if y == 1 or y == x - 1:
continue
for _ in range(s - 1):
y = y * y % x
if y == x - 1:
break
else:
return False
return True
n = int(input())
if n % 2 != 0:
q = deque(["2", "3", "5", "7"])
i = 1
else:
q = deque(["22", "33", "55", "77"])
i = 2
while i != n:
while q:
s = q[0]
if len(s) == n:
break
q.popleft()
for c in "2357":
q.append(c + s + c)
i += 2
cnt = 0
while q:
if is_prime(int(q.popleft())):
cnt += 1
print(cnt)Ở code trên do các giá trị trong hàng đợi đang là kiểu chuỗi nên khi gọi vào hàm kiểm tra số nguyên tố thì ta phải đổi chuỗi thành số nhờ hàm stoll (string to long long).
while(!q.empty()) bên trong chỉ dừng khi gặp chuỗi có độ dài đúng bằng $N$, nên ngay ở lượt đầu tiên của vòng while(i != n) nó đã sinh liền một mạch qua tất cả các tầng $1 \to 3 \to 5 \to \dots \to N$. Các lượt sau của vòng ngoài chỉ gặp ngay break và tăng $i$ cho tới khi $i = N$. Ví dụ $N = 5$: lượt đầu của vòng ngoài lấy ra 4 chuỗi độ dài 1 rồi tiếp 16 chuỗi độ dài 3, dừng khi đầu hàng đợi là "22222"; lượt thứ hai ($i = 3$) gặp break ngay; sau đó $i = 5$ thì thoát. Kết quả vẫn hoàn toàn đúng.Với $X = \frac{N}{2}$ nếu $N$ chẵn hoặc $X = \frac{N}{2} + 1$ nếu $N$ lẻ (chia nguyên), còn $Y$ là độ phức tạp của bước kiểm tra số nguyên tố với từng số trong tập $4^X$ số, tức là $O(\sqrt{10^N})$ cho mỗi số. Thời gian là $O(4^1 + 4^2 + \dots + 4^X)$ $+ O(4^X \cdot Y)$.
Bản Python mình viết thêm dùng thuật kiểm tra nguyên tố Miller–Rabin (với $x < 3{,}4 \cdot 10^{12}$ chỉ cần thử 6 cơ số 2, 3, 5, 7, 11, 13 là chính xác tuyệt đối), vì nếu thử chia đến $\sqrt{x}$ như bản C++ thì Python mất gần 5 giây với $N = 11$.
MẹoĐặt sẵn đáp án vào mảng – O(1)
Code ở trên nếu chạy thử ta sẽ có kết luận đáp án tương ứng của từng trường hợp $N$ như sau:
| N | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Đáp án | 4 | 0 | 4 | 0 | 11 | 0 |
| N | 7 | 8 | 9 | 10 | 11 | 12 |
| Đáp án | 18 | 0 | 77 | 0 | 218 | 0 |
Vậy nên nếu bạn nào sợ code ở trên lỡ chạy mà có quá giới hạn 1 giây vì lý do gì đó (ví dụ máy tính chấm ngay thời điểm đó bị yếu đột xuất chẳng hạn 🤪) thì chúng ta có thể chơi mẹo: khi đã chạy chương trình trên máy tính biết được đáp án của 12 trường hợp $N$ rồi thì đưa trực tiếp nó vào bài làm luôn:
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[] = {-1, 4, 0, 4, 0, 11, 0, 18, 0, 77, 0, 218, 0};
int n;
cin >> n;
cout << a[n];
return 0;
}a = [-1, 4, 0, 4, 0, 11, 0, 18, 0, 77, 0, 218, 0]
n = int(input())
print(a[n])Ta tạo mảng 13 phần tử (bỏ không dùng index 0), chỉ dùng các index từ 1 đến 12, để với giá trị $N$ ta gọi vào giá trị tại index $N$ chính là đáp số. Làm như thế này không ai bắt bẻ được chúng ta vì rõ ràng sẽ ra đáp án đúng như đề bài cần hihi, và chắc chắn cách này sẽ chạy nhanh nhất luôn rồi 😁
Không gian $O(1)$ vì mảng chỉ có 13 phần tử, là hằng số cố định. Thời gian $O(1)$ vì chỉ 1 phép truy xuất vị trí index $N$.