Hướng dẫn giải của Nguyên tố Mersenne
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 toán yêu cầu đếm số lượng số nguyên tố Mersenne nằm trong đoạn [a, b]. Số nguyên tố Mersenne là số nguyên tố có dạng 2^n - 1. Dải giá trị của a, b lên tới 2^31 - 1 (khoảng 2 tỷ).
Các cách tiếp cận
Cách Brute Force (Lặp và Kiểm tra)
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
if (n < 2) return false;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
long long a, b;
cin >> a >> b;
int count = 0;
long long p = 2;
while (true) {
long long val = p - 1;
if (val > b) break;
if (val >= a && isPrime(val)) {
count++;
}
if (p > 2e9) break; // Tránh tràn số
p *= 2;
}
cout << count;
return 0;
}
- Time Complexity: O(sqrt(b))
- Space Complexity: O(1)
Phương pháp này tạo ra các số 2^n - 1 bằng cách nhân đôi p (bắt đầu từ 2). Với mỗi số tạo ra, nó kiểm tra xem số đó có phải là số nguyên tố bằng cách lặp từ 2 đến căn bậc hai của nó. Tuy nhiên, đoạn code mẫu trong bài nộp bị lỗi logic (kiểm tra i-1 thay vì 2^i-1 và không kiểm tra số nguyên tố đúng cách), đây là cách tiếp cận sai lầm thường gặp. Cách này rất chậm nếu dải giá trị lớn, nhưng với a, b <= 2^31-1 thì số lượng số Mersenne cần kiểm tra rất ít (chỉ khoảng 31 số), nên nó có thể chạy nhanh nếu viết đúng.
Cách Precompute (Tính toán trước)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
// Danh sách các số nguyên tố Mersenne nhỏ hơn 2^31 - 1
long long M[] = {
3LL, // 2^2 - 1
7LL, // 2^3 - 1
31LL, // 2^5 - 1
127LL, // 2^7 - 1
8191LL, // 2^13 - 1
131071LL, // 2^17 - 1
524287LL, // 2^19 - 1
2147483647LL // 2^31 - 1
};
int cnt = 0;
for (long long x : M) {
if (a <= x && x <= b) cnt++;
}
cout << cnt;
return 0;
}
- Time Complexity: O(1)
- Space Complexity: O(1)
Đây là phương pháp tối ưu nhất cho bài toán này. Biết rằng số nguyên tố Mersenne là 2^n - 1, và 2^n - 1 chỉ có thể là số nguyên tố khi n là số nguyên tố (định lý Lucas-Lehmer không bắt buộc ở đây, nhưng ta biết có rất ít số Mersenne nguyên tố). Với giới hạn b <= 2^31 - 1, n không vượt quá 31. Ta có thể liệt kê tất cả các số nguyên tố Mersenne nhỏ hơn 2^31 - 1 (chỉ có 8 số) và lưu vào mảng. Sau đó chỉ cần đếm số lượng số trong mảng nằm trong đoạn [a, b].
Cách Tối ưu hóa Brute Force (Kiểm tra nguyên tố bằng Fermat/Miller-Rabin)
#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using u128 = __uint128_t;
u64 power(u64 base, u64 exp, u64 mod) {
u64 res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (u128)res * base % mod;
base = (u128)base * base % mod;
exp /= 2;
}
return res;
}
bool miller_rabin(u64 n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;
u64 d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
// Các số a để kiểm tra cho n < 2^32
static const u64 bases[] = {2, 7, 61};
for (u64 a : bases) {
if (a >= n) break;
u64 x = power(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
int main() {
long long a, b;
cin >> a >> b;
int count = 0;
long long p = 4; // Bắt đầu từ 2^2
// 2^31 - 1 là số lớn nhất có thể
while (p - 1 <= b) {
long long val = p - 1;
if (val >= a) {
// Chỉ kiểm tra nếu n là số nguyên tố (điều kiện cần cho Mersenne prime)
// Tuy nhiên, ta vẫn phải kiểm tra tính nguyên tố của val
if (miller_rabin(val)) {
count++;
}
}
if (p > 2e9) break; // Guard
p *= 2;
}
cout << count;
return 0;
}
- Time Complexity: O(1) per check (vì số lượng số cần kiểm tra rất ít)
- Space Complexity: O(1)
Sử dụng thuật toán Miller-Rabin để kiểm tra tính nguyên tố nhanh chóng cho các số lớn (2^31 - 1 là số 32-bit nên Miller-Rabin với cơ số 2, 7, 61 là đủ để xác định chắc chắn). Tạo các số 2^n - 1 và kiểm tra. Cách này tổng quát hơn Precompute nhưng vẫn nhanh.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(sqrt(b)) | O(1) | Brute Force (Lặp và Kiểm tra) |
| 2 | O(1) | O(1) | Precompute (Tính toán trước) |
| 3 | O(1) per check (vì số lượng số cần kiểm tra rất ít) | O(1) | Tối ưu hóa Brute Force (Kiểm tra nguyên tố bằng Fermat/Miller-Rabin) |
Bài học kinh nghiệm
- Số lượng số nguyên tố Mersenne nhỏ hơn 2^31 - 1 rất ít (chỉ 8 số), do đó giải pháp Precompute (liệt kê thủ công) là hiệu quả và an toàn nhất.
- Dải giá trị a, b khá lớn (lên tới 2 tỷ) nhưng số lượng số Mersenne trong dải này rất ít, nên bài toán không yêu cầu tìm kiếm hay sàng số nguyên tố trong dải.
Lỗi thường gặp
- Lỗi tràn số khi tính 2^n với n lớn (ví dụ n > 62). Cần kiểm soát giá trị của n hoặc giá trị 2^n.
- Lỗi logic trong việc sinh số Mersenne (tính sai công thức 2^n - 1) hoặc kiểm tra tính nguyên tố không đầy đủ cho các số lớn.
Bình luận