Hướng dẫn giải của Phú yên_ bài 1
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Đề bài yêu cầu tìm các số nguyên tố đặc biệt (super primes) có đúng n chữ số. Một số được coi là 'nguyên tố đặc biệt' nếu tất cả các tiền tố của nó (các số tạo thành bằng cách bỏ các chữ số cuối cùng) đều là số nguyên tố. Ví dụ, với n=3, số 233 là nguyên tố đặc biệt vì 2, 23, và 233 đều là số nguyên tố. Input là một số nguyên n (1 <= n <= 9), output là danh sách các số nguyên tố đặc biệt có đúng n chữ số.
Các cách tiếp cận
Cách Backtracking (Quay lui)
#include <iostream>
#include <fstream>
using namespace std;
int n;
int digits[] = {1, 3, 5, 7, 9}; // Only odd digits can be appended to a prime > 2
bool isPrime(int x) {
if (x < 2) return false;
if (x == 2 || x == 3) return true;
if (x % 2 == 0 || x % 3 == 0) return false;
for (int i = 5; i * i <= x; i += 6) {
if (x % i == 0 || x % (i + 2) == 0) return false;
}
return true;
}
void backtrack(int len, int currentNum) {
if (len == n) {
if (isPrime(currentNum)) {
cout << currentNum << "\n";
}
return;
}
for (int d : digits) {
int nextNum = currentNum * 10 + d;
if (isPrime(nextNum)) {
backtrack(len + 1, nextNum);
}
}
}
int main() {
freopen("bai1.inp", "r", stdin);
freopen("bai1.out", "w", stdout);
cin >> n;
// Start with initial primes of 1 digit
if (n >= 1) backtrack(1, 2);
if (n >= 1) backtrack(1, 3);
if (n >= 1) backtrack(1, 5);
if (n >= 1) backtrack(1, 7);
return 0;
}
- Time Complexity: O(N * 10^N) (thực tế nhỏ hơn nhiều)
- Space Complexity: O(N)
Tiếp cận này sử dụng đệ quy (backtracking). Nó bắt đầu từ các số nguyên tố 1 chữ số (2, 3, 5, 7) và lần lượt thêm các chữ số lẻ (1, 3, 5, 7, 9) vào bên phải. Nếu số mới tạo thành là số nguyên tố, đệ quy tiếp tục. Khi độ dài đạt n, số đó được in ra. Cách này hiệu quả vì chỉ kiểm tra các số có khả năng là nguyên tố đặc biệt.
Cách Brute Force (Sàng Eratosthenes)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
const int MAX = 100000000;
vector<bool> sieve() {
vector<bool> isPrime(MAX, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < MAX; i++) {
if (isPrime[i]) {
for (int j = i * i; j < MAX; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
bool check(long long x, const vector<bool>& isPrime) {
if (x >= MAX) return false; // Out of range for sieve
if (!isPrime[x]) return false;
while (x > 0) {
if (!isPrime[x]) return false;
x /= 10;
}
return true;
}
int main() {
ifstream fileIn("BAI1.INP");
ofstream fileOut("BAI1.OUT");
int n;
fileIn >> n;
vector<bool> isPrime = sieve();
int lower = pow(10, n-1);
int upper = pow(10, n) - 1;
for (int i = lower; i <= upper; i++) {
if (check(i, isPrime)) {
fileOut << i << "\n";
}
}
return 0;
}
- Time Complexity: O(10^N log log 10^N)
- Space Complexity: O(10^N)
Tiếp cận này tạo một mảng sàng (sieve) để đánh dấu các số nguyên tố từ 1 đến 10^N. Sau đó, nó duyệt qua tất cả các số trong khoảng từ 10^(N-1) đến 10^N - 1. Với mỗi số, nó kiểm tra xem số đó và tất cả các prefix của nó có phải là số nguyên tố không bằng cách tra cứu mảng sàng. Cách này đơn giản nhưng tốn bộ nhớ và thời gian nếu N lớn.
Cách Optimized Generation
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
void findSuperPrimes(int n, vector<int>& superPrimes) {
if (n == 1) {
for (int i = 2; i < 10; ++i) {
if (isPrime(i)) {
superPrimes.push_back(i);
}
}
return;
}
vector<int> prevSuperPrimes;
findSuperPrimes(n - 1, prevSuperPrimes);
for (int num : prevSuperPrimes) {
for (int digit = 1; digit < 10; digit += 2) { // Only odd digits
int newNum = num * 10 + digit;
if (isPrime(newNum)) {
superPrimes.push_back(newNum);
}
}
}
}
int main() {
ifstream infile("BAI1.INP");
ofstream outfile("BAI1.OUT");
int n;
infile >> n;
vector<int> result;
findSuperPrimes(n, result);
for (int p : result) {
outfile << p << "\n";
}
return 0;
}
- Time Complexity: Tương tự Backtracking
- Space Complexity: O(Số lượng kết quả)
Đây là biến thể của Backtracking nhưng thay vì đệ quy, nó xây dựng các số nguyên tố đặc biệt theo độ dài. Bắt đầu từ độ dài 1, nó tạo ra tất cả số nguyên tố đặc biệt độ dài 1, rồi dùng chúng để tạo số độ dài 2, v.v.直到 độ dài n. Cách này kiểm soát quá trình tạo số rõ ràng hơn và chỉ tạo ra các số có khả năng hợp lệ.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * 10^N) (thực tế nhỏ hơn nhiều) | O(N) | Backtracking (Quay lui) |
| 2 | O(10^N log log 10^N) | O(10^N) | Brute Force (Sàng Eratosthenes) |
| 3 | Tương tự Backtracking | O(Số lượng kết quả) | Optimized Generation |
Bài học kinh nghiệm
- Chữ số cuối cùng của một số nguyên tố lớn hơn 5 phải là 1, 3, 7, hoặc 9 (vì nếu chia hết cho 2 hoặc 5 thì không phải nguyên tố). Điều này giảm đáng kể không gian tìm kiếm.
- Để kiểm tra một số có phải là 'super prime' hay không, ta chỉ cần kiểm tra các tiền tố của nó. Nếu ta xây dựng số từ trái sang phải và chỉ giữ lại các số là nguyên tố tại mỗi bước, ta đảm bảo tính chất này.
- Với n nhỏ (≤ 9), Backtracking là lựa chọn tối ưu nhất về cả thời gian và bộ nhớ so với việc sàng số nguyên tố lên đến 10^9.
Lỗi thường gặp
- Quên kiểm tra các tiền tố khi tạo số mới. Ví dụ, thêm chữ số vào số không nguyên tố sẽ không bao giờ tạo ra số nguyên tố đặc biệt.
- Lỗi số học khi tính toán 10^n cho n lớn nếu không dùng đúng kiểu dữ liệu (dù n≤9 thì int vẫn ổn).
- Đối với phương pháp sàng, mảng 10^9 bool (~1GB) có thể gây tràn bộ nhớ hoặc chậm nếu không tối ưu (ví dụ dùng vector<bool>).
Bình luận