Nguồn: LuyenCodeĐộ khó: Trung bìnhSố nguyên tốHàng đợi
Đề bài
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ: $7331$ là một số siêu nguyên tố có $4$ chữ số vì $733$, $73$, $7$ cũng là các số nguyên tố.
Hiếu tình cờ nhặt được số nguyên dương $n$, và tự hỏi có bao nhiêu số siêu nguyên tố có $n$ chữ số. Bạn hãy giúp Hiếu giải đáp câu hỏi trên nhé!
Dữ liệu vào: số nguyên dương $n$ ($1 \le n \le 10$).
Dữ liệu ra: in ra các số siêu nguyên tố có $n$ chữ số trên cùng $1$ dòng, cách nhau $1$ kí tự trắng.
Ví dụ – input
1
Ví dụ – output
2 3 5 7
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức, kèm theo đó là toàn bộ tin nhắn của mình với em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Bài này các bạn có thể xem đề và nộp tại đây nha:
Dành cho tất cả mọi ngườiNộp bài trên LuyenCode
Link này công khai, bạ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.
Đầu tiên em ấy cho mình xem code bài làm, đi theo đúng như định nghĩa đề bài: viết hàm kiểm tra số $X$ bất kỳ có phải số nguyên tố không, sau đó duyệt qua toàn bộ các số có $n$ chữ số (ví dụ $n = 4$ thì xét từ 1000 đến 9999). Với mỗi số thì loại bỏ dần từng chữ số bên phải và kiểm tra phần còn lại có còn là số nguyên tố không, nếu tất cả đều thoả thì đó là số siêu nguyên tố. Ví dụ 1234 thì xét 1234, 123, 12, 1.
HV
“Em làm đúng như đề: duyệt hết các số có N chữ số, bỏ dần chữ số bên phải rồi kiểm tra nguyên tố, mà sao hệ thống báo TLE vậy anh? Anh hướng dẫn em cách làm với ạ.”
Nếu làm như cách trên của em thì với $n$ tối đa là 10 như đề bài cho, nghĩa là lặp từ 1 tỷ đến 10 tỷ → lặp 9 tỷ lần. Mình còn chưa tính chi phí với mỗi số phải đi loại bỏ dần bên phải, rồi mỗi số đó còn phải kiểm tra nguyên tố. Chỉ nói riêng việc lặp 9 tỷ lần: máy tính phổ thông 1 giây lặp được khoảng 30 đến 50 triệu lần, tức $(3 \text{ đến } 5) \cdot 10^7$. Cho 1 giây được $5 \cdot 10^7$ đi thì $\frac{9 \cdot 10^9}{5 \cdot 10^7} \approx 200$ giây. Trong khi bài này chỉ cho 20 ms 🤣 tức là $\frac{1}{50}$ giây! Nội việc lặp 9 tỷ lần đã cần ít nhất 200 giây, chưa kể còn đống bước xử lý sau đó, không TLE mới lạ 😝
Ngưỡng cho 20 ms
$\frac{5 \cdot 10^7}{50} = 10^6$. Nghĩa là toàn bài từ đầu (input) đến hết bước xử lý ra kết quả, tính trong trường hợp xấu nhất ($n = 10$), mà tổng số lần lặp tầm 1 triệu đổ lại thì yên tâm chạy trong 20 ms; quá ngưỡng đó thì 20 ms không chịu nổi đâu.
Bài này không thể nào xét hết toàn bộ các số có $n$ chữ số như thế. Em hãy nghĩ ra một cách khác sao cho số lượng số cần xét giảm đi thật nhiều dựa trên định nghĩa của số này nhé. Phải nói là giảm đi rất rất nhiều, không cần xét hết mà chỉ một số rất ít thôi 😁
Ý tưởngKiểm tra từ số nhỏ, sinh dần từ trái sang phải
Dưới đây là hướng giải mình nói ra luôn sau khi em ấy vẫn chưa giải quyết được.
Giả sử cần liệt kê tất cả các số siêu nguyên tố có 5 chữ số. Số có 5 chữ số sẽ có dạng $\overline{abcde}$, thì nó phải thoả tất cả:
abcde2nguyên tố ✓
abcde23nguyên tố ✓
abcde235không ✗ – dừng!
abcde2357khỏi xét
abcde23579khỏi xét
Thì chắc chắn ta sẽ cần một hàm kiểm tra số $X$ bất kỳ có là số nguyên tố không. Vấn đề là $X$ càng lớn thì hàm đó càng phải chạy nhiều và lâu.
Quay lại ví dụ số 23579. Em có nghĩ là cần phải kiểm tra cả số 23579 ngay từ đầu không? Một cách làm thông minh hơn là kiểm tra các số thật nhỏ trước, nếu thoả thì mới đi kiểm tra số lớn hơn, còn không thoả thì khỏi kiểm tra luôn. Với 23579: kiểm tra 2 thoả → kiểm tra tiếp 23 thoả → kiểm tra tiếp 235 không thoả → dừng, khỏi mất công kiểm tra 2357, 23579 làm gì. Hay với số 45793: ngay từ đầu 4 đã không phải số nguyên tố thì dừng luôn, khỏi xét 45, 457, 4579, 45793.
Sinh dần từng tầng
Đầu tiên tạo danh sách có 4 số: 2, 3, 5, 7 – đây chính là 4 số siêu nguyên tố có 1 chữ số.
Từ 4 số này sinh ra các số siêu nguyên tố có 2 chữ số bằng cách ghép thêm 1 chữ số vào bên phải. Ta không cần xét chữ số chẵn (0, 2, 4, 6, 8) vì khi đó số mới chia hết cho 2, chắc chắn không phải số nguyên tố. Nên ví dụ với số 2, không cần xét 20, 22, 24, 26, 28 mà chỉ xét với các chữ số lẻ 1, 3, 5, 7, 9: 21, 23, 25, 27, 29 – thằng nào là nguyên tố thì giữ lại.
Tương tự với 3 xét 31, 33, 35, 37, 39; với 5 xét 51, 53, 55, 57, 59; với 7 xét 71, 73, 75, 77, 79.
Trong 21, 23, 25, 27, 29 thì 23, 29 thoả → giữ lại để sinh tầng 3 chữ số: từ 23 sinh 231, 233, 235, 237, 239; từ 29 sinh 291, 293, 295, 297, 299...
Cứ thế sinh liên tục đến khi được các số có đủ $n$ chữ số thì dừng, in ra toàn bộ các số đó.
Vì sao cách này đúng?
Mọi số siêu nguyên tố $n$ chữ số, khi bỏ chữ số cuối, đều là số siêu nguyên tố $n - 1$ chữ số. Nên chỉ cần sinh từ các số siêu nguyên tố của tầng trước là không bỏ sót số nào; và mỗi số sinh ra đều đã được kiểm tra đủ mọi tiền tố nên không thừa.
Số chữ số
1
2
3
4
5
6
7
8
9
10
Số lượng số siêu nguyên tố
4
9
14
16
15
12
8
5
0
0
Bảng trên cho thấy số lượng cần xét cực kỳ ít: mỗi tầng chỉ có vài chục số, tầng 9 thì không còn số nào (5 số 8 chữ số ghép thêm chữ số nào cũng không ra số nguyên tố) nên tầng 10 cũng rỗng luôn.
Minh hoạCây sinh số siêu nguyên tố
Em nhập $n$ (từ 1 đến 6) rồi bấm Tiếp để xem mỗi số ở tầng trước được ghép thêm 1, 3, 5, 7, 9 như thế nào, số nào là nguyên tố thì được giữ lại cho tầng sau:
Ví dụ nhanh:
CodeHai hàng đợi q, q2 – sinh theo tầng
Source code giải quyết theo tư tưởng mình đã trình bày ở trên và cũng đã nộp thành công trên web, các bạn xem để hiểu rõ hơn. Hàng đợi q chứa các số siêu nguyên tố của tầng hiện tại, còn q2 dùng để chứa các số của tầng kế tiếp; xử lý xong một tầng thì gán q = q2 và làm rỗng q2, biến cnt đếm số chữ số hiện có:
#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(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n;
cin >> n;
queue<long long> q, q2;
q.push(2LL);
q.push(3LL);
q.push(5LL);
q.push(7LL);
long long cnt = 1;
while(cnt < n){
while(!q.empty()){
long long x = q.front();
q.pop();
if(isPrime(x * 10 + 1)){
q2.push(x * 10 + 1);
}
if(isPrime(x * 10 + 3)){
q2.push(x * 10 + 3);
}
if(isPrime(x * 10 + 5)){
q2.push(x * 10 + 5);
}
if(isPrime(x * 10 + 7)){
q2.push(x * 10 + 7);
}
if(isPrime(x * 10 + 9)){
q2.push(x * 10 + 9);
}
}
q = q2;
queue<long long> q_empty;
swap(q2, q_empty);
cnt++;
}
while(!q.empty()){
cout << q.front() << " ";
q.pop();
}
return 0;
}
from collections import deque
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
for i in range(2, int(x**0.5) + 1):
if x % i == 0:
return False
return True
n = int(input())
q = deque([2, 3, 5, 7])
q2 = deque()
cnt = 1
while cnt < n:
while q:
x = q.popleft()
for d in [1, 3, 5, 7, 9]:
new_num = x * 10 + d
if is_prime(new_num):
q2.append(new_num)
q = q2
q2 = deque()
cnt += 1
for num in q:
print(num, end=' ')
C++▶ Chạy tay từng dòng codeSinh dần các số siêu nguyên tố theo tầng bằng 2 hàng đợi q, q2.
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3bool isPrime(longlong x){
4for(longlong i = 2; i * i <= x; i++){
5if(x % i == 0){
6returnfalse;
7 }
8 }
9return x >= 2;
10}
11int main(){
12ios::sync_with_stdio(0);
13cin.tie(0);
14longlong n;
15cin >> n;
16queue<longlong> q, q2;
17 q.push(2LL);
18 q.push(3LL);
19 q.push(5LL);
20 q.push(7LL);
21longlong cnt = 1;
22while(cnt < n){
23while(!q.empty()){
24longlong x = q.front();
25 q.pop();
26if(isPrime(x * 10 + 1)){
27 q2.push(x * 10 + 1);
28 }
29if(isPrime(x * 10 + 3)){
30 q2.push(x * 10 + 3);
31 }
32if(isPrime(x * 10 + 5)){
33 q2.push(x * 10 + 5);
34 }
35if(isPrime(x * 10 + 7)){
36 q2.push(x * 10 + 7);
37 }
38if(isPrime(x * 10 + 9)){
39 q2.push(x * 10 + 9);
40 }
41 }
42 q = q2;
43queue<longlong> q_empty;
44swap(q2, q_empty);
45 cnt++;
46 }
47while(!q.empty()){
48cout << q.front() << " ";
49 q.pop();
50 }
51return0;
52}
Đánh giá độ phức tạp: cả bài chỉ có 83 số siêu nguyên tố (từ 1 đến 8 chữ số), nên tổng số lần gọi isPrime chỉ khoảng $5 \times 83 \approx 400$ lần, mỗi lần tối đa $\sqrt{X} \le 10^5$ vòng lặp. Thực tế phần lớn số bị loại ngay ở vài ước nhỏ đầu tiên, nên toàn bài chạy nhanh hơn ngưỡng $10^6$ rất nhiều.
Không gian$O(S)$ với $S$ là số lượng số siêu nguyên tố trong 1 tầng
Thời gian$O(5 \cdot S_{tong} \cdot \sqrt{X})$, rất nhỏ
Kết quả kiểm tra: code C++ và Python của mình được so với cách vét cạn (duyệt mọi số có $n$ chữ số, bỏ dần chữ số bên phải và kiểm tra nguyên tố) cho mọi $n$ từ 1 đến 8 – khớp hết. Vì $n$ chỉ có 10 giá trị nên mình chạy đủ cả 10 trường hợp: với $n = 9$ và $n = 10$ không có số nào nên chương trình in dòng trống. Với $n = 10$ bản C++ chạy khoảng 4 ms, bản Python khoảng 0,03 giây.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
Nguồn: Codeforces GroupĐộ khó: Trung bìnhSố nguyên tốSố đối xứngHàng đợi
Đề 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.
Ví dụ – input
1
Ví dụ – output
4
Giả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 😇.
Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ
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.
Bạ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.
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)
C++▶ Chạy tay từng dòng codeVét cạn: xét mọi số từ 10^(n−1) đến 10^n − 1, kiểm tra đối xứng, nguyên tố, từng chữ số.
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13bool isPalind(longlong x){
14longlong rever = 0;
15longlong temp = x;
16while(temp){
17 rever = rever * 10 + temp % 10;
18 temp /= 10;
19 }
20return rever == x;
21}
22
23bool isPerfectPrime(longlong x){
24if(!isPalind(x) || !isPrime(x)){
25returnfalse;
26 }
27while(x){
28if(!isPrime(x % 10)){
29returnfalse;
30 }
31 x /= 10;
32 }
33returntrue;
34}
35
36int main(){
37int n;
38cin >> n;
39longlong start = (longlong)pow(10.0, n - 1);
40longlong finish = (longlong)pow(10.0, n) - 1;
41longlong cnt = 0;
42for(longlong i = start; i <= finish; ++i){
43if(isPerfectPrime(i)){
44 cnt++;
45 }
46 }
47cout << cnt;
48return0;
49}
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ược rever bằng cách liên tục lấy chữ số cuối temp % 10 gắn vào sau rever, rồi so rever == x.
isPerfectPrime(x): phải đối xứng, phải nguyên tố, rồi tách từng chữ số x % 10 kiểm tra cũng phải nguyên tố.
Không gian$O(1)$
Thời gian$O((10^N - 10^{N-1}) \cdot X)$
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$
Quy luật tổng quát
Với $N \ge 3$ (riêng $N = 1, 2$ ta chủ động để sẵn), các số cần xét gồm tất cả các trường hợp của $N - 2$, mỗi trường hợp lần lượt được kẹp giữa bởi 2 đầu là các chữ số 2, 3, 5, 7. Số lượng: $N = 1, 2$ có 4 số; với $N \ge 3$ thì có $4 \times$ (số lượng của trường hợp $N - 2$).
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?
Mình bổ sung thêm một nhận xét thú vị: cột đáp án cho thấy với mọi $N$ chẵn thì đáp án đều bằng 0. Lý do là mọi số đối xứng có số chữ số chẵn đều chia hết cho 11 (tổng các chữ số ở vị trí lẻ bằng tổng các chữ số ở vị trí chẵn, ví dụ $2332 = 11 \times 212$). Số duy nhất như vậy là số nguyên tố chính là 11, mà 11 lại chứa chữ số 1 không nguyên tố. Vì vậy $N$ chẵn thì không có số nguyên tố hoàn hảo nào.
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ản y = "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 2 ra (độ dài 1 khác 3) → sinh 222 323 525 727. Hàng đợi: 3 5 7 222 323 525 727.
Lấy 3 ra → sinh 232 333 535 737. Hàng đợi: 5 7 222 323 525 727 232 333 535 737.
Lấy 5 ra → sinh 252 353 555 757. Hàng đợi: 7 222 … 737 252 353 555 757.
Lấy 7 ra → sinh 272 373 575 777. Hàng đợi giờ chứa đúng 16 số có 3 chữ số.
Đầu hàng đợi là 222 có độ 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ố:
Ví dụ nhanh:
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)
C++▶ Chạy tay từng dòng codeSinh các số đối xứng chỉ gồm 2, 3, 5, 7 bằng hàng đợi, rồi kiểm tra nguyên tố từng số.
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2usingnamespace std;
3
4bool isPrime(longlong x){
5for(longlong i = 2; i * i <= x; ++i){
6if(x % i == 0){
7returnfalse;
8 }
9 }
10return x >= 2;
11}
12
13int main(){
14int n;
15cin >> n;
16queue<string> q;
17int i;
18if(n % 2 != 0){
19 q.push("2");
20 q.push("3");
21 q.push("5");
22 q.push("7");
23 i = 1;
24 }
25else{
26 q.push("22");
27 q.push("33");
28 q.push("55");
29 q.push("77");
30 i = 2;
31 }
32while(i != n){
33while(!q.empty()){
34string s = q.front();
35if(s.length() == n){
36break;
37 }
38 q.pop();
39 q.push("2" + s + "2");
40 q.push("3" + s + "3");
41 q.push("5" + s + "5");
42 q.push("7" + s + "7");
43 }
44 i += 2;
45 }
46int cnt = 0;
47while(!q.empty()){
48if(isPrime(stoll(q.front()))){
49 cnt++;
50 }
51 q.pop();
52 }
53cout << cnt;
54return0;
55}
Ở 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).
Một chi tiết nhỏ khi chạy tay code: vòng 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.
Không gian$O(4^X)$
Thời gian$O(4^X \cdot \sqrt{10^N})$
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])
C++▶ Chạy tay từng dòng codeMẹo: đặt sẵn 12 đáp án vào mảng, in a[n] – O(1).
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)$
Thời gian$O(1)$
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$.
Ghi chú kiểm tra của mình: cả 3 bản C++ và 3 bản Python đã được mình biên dịch, chạy lại. Đáp án của cả 12 giá trị $N$ được đối chiếu với một chương trình độc lập (sinh mọi số đối xứng $N$ chữ số rồi kiểm tra bằng Miller–Rabin), thêm 220 lần chạy với $N$ ngẫu nhiên so sánh cách hàng đợi và cách đặt sẵn, trong đó 126 lần $N \le 7$ so trực tiếp với code vét cạn. Thời gian trên máy mình: vét cạn C++ mất 0.18 giây với $N = 7$, 1.7 giây với $N = 8$ và 17.6 giây với $N = 9$; cách hàng đợi C++ mất 0.19 giây với $N = 11$ (trường hợp nặng nhất); bản Python Miller–Rabin chỉ 0.03 giây; cách đặt sẵn thì tức thì.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
