Hướng dẫn giải của fibonaci_nguyên_tố
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
Cho hai số nguyên dương N và M (1 ≤ N ≤ M). Yêu cầu đếm số lượng số Fibonacci nằm trong khoảng [N, M] là số nguyên tố. Ghi chú: Dãy Fibonacci được định nghĩa là F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ (n ≥ 3). Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó.
Các cách tiếp cận
Cách Sinh dãy Fibonacci và kiểm tra thủ công
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
if(x < 2) return false;
if(x % 2 == 0) return x == 2;
for(long long i = 3; i * i <= x; i += 2)
if(x % i == 0) return false;
return true;
}
int main(){
freopen("fibo.inp","r",stdin);
freopen("fibo.out","w",stdout);
long long n, m;
cin >> n >> m;
vector<long long> f;
long long a = 1, b = 1;
f.push_back(1);
f.push_back(1);
while(true){
long long c = a + b;
if(c > m) break;
f.push_back(c);
a = b;
b = c;
}
int cnt = 0;
for(long long x : f)
if(x >= n && x <= m && isPrime(x))
cnt++;
cout << cnt;
}
- Time Complexity: O(√M * log M)
- Space Complexity: O(log M)
Approach này sinh ra tất cả các số Fibonacci nhỏ hơn hoặc bằng M và lưu chúng vào một vector. Sau đó, nó duyệt qua vector này, kiểm tra xem số nào nằm trong khoảng [N, M] và đồng thời là số nguyên tố. Việc sinh dãy Fibonacci rất nhanh vì số lượng số Fibonacci nhỏ hơn M là rất ít (khoảng 45 số nếu M ≤ 10^9). Việc kiểm tra nguyên tố được thực hiện trong thời gian O(√x).
Cách Sinh dãy Fibonacci và kiểm tra trong lúc sinh (Tiết kiệm bộ nhớ)
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int x) {
if (x < 2) return false;
if (x == 2) return true;
if (x % 2 == 0) return false;
for (int i = 3; i * i <= x; i += 2)
if (x % i == 0) return false;
return true;
}
int main() {
ifstream fin("FIBO.INP");
ofstream fout("FIBO.OUT");
int n, m;
fin >> n >> m;
int a = 1, b = 1;
int count = 0;
// F1 = 1 (không phải nguyên tố)
// F2 = 1 (không phải nguyên tố)
while (b <= m) {
if (b >= n && isPrime(b)) count++;
int c = a + b;
a = b;
b = c;
}
fout << count << "\n";
fin.close();
fout.close();
return 0;
}
- Time Complexity: O(√M * log M)
- Space Complexity: O(1)
Cách tiếp cận này tối ưu hơn về bộ nhớ. Thay vì lưu trữ cả dãy Fibonacci, ta chỉ cần duy trì 2 biến để tính toán số Fibonacci tiếp theo. Trong mỗi bước lặp, ta kiểm tra ngay số Fibonacci hiện tại (b) xem có nằm trong khoảng [N, M] và có phải là số nguyên tố không. Nếu có thì tăng biến đếm. Vòng lặp dừng lại khi số Fibonacci tính được vượt quá M.
Cách Tối ưu hóa với Precomputation (Khuyến nghị)
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
// Hàm kiểm tra số nguyên tố nhanh O(sqrt(n))
bool isPrime(long long n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
int main() {
// Tạo danh sách các số Fibonacci là số nguyên tố (trước khi giải quyết test case)
vector<long long> primeFib;
long long a = 1, b = 1;
// Chỉ kiểm tra các số Fibonacci >= 2
// F1=1, F2=1 không phải nguyên tố
// F3=2 là số nguyên tố
if (isPrime(2)) primeFib.push_back(2);
while (true) {
long long c = a + b;
if (c > 2000000000LL) break; // Giả sử M tối đa là 2 tỷ
if (isPrime(c)) primeFib.push_back(c);
a = b;
b = c;
}
// Đọc input
long long N, M;
if (fopen("FIBO.INP", "r")) {
freopen("FIBO.INP", "r", stdin);
freopen("FIBO.OUT", "w", stdout);
}
if (cin >> N >> M) {
// Đếm số lượng số trong khoảng [N, M]
// Sử dụng lower_bound và upper_bound để đếm nhanh
auto it1 = lower_bound(primeFib.begin(), primeFib.end(), N);
auto it2 = upper_bound(primeFib.begin(), primeFib.end(), M);
cout << (it2 - it1) << endl;
}
return 0;
}
- Time Complexity: O(1) với mỗi query (do dãy Fibonacci nguyên tố rất ngắn)
- Space Complexity: O(log K) (K là số lượng Fibonacci nguyên tố)
Trong các kỳ thi lập trình, t tổng số Fibonacci nguyên tố nhỏ hơn 10^9 chỉ có 3 số (2, 3, 5). Ngay cả khi M lên tới hàng tỷ, số lượng Fibonacci nguyên tố vẫn rất hạn chế. Do đó, ta có thể precompute (tính trước) toàn bộ các số Fibonacci là số nguyên tố nằm trong giới hạn cho phép của đề bài. Khi nhận input N, M, ta chỉ cần dùng kỹ thuật Binary Search (lowerbound, upperbound) để đếm số lượng phần tử trong mảng đã precomputed nằm trong khoảng [N, M]. Cách này đảm bảo thời gian chạy là nhanh nhất cho mỗi test case.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(√M * log M) | O(log M) | Sinh dãy Fibonacci và kiểm tra thủ công |
| 2 | O(√M * log M) | O(1) | Sinh dãy Fibonacci và kiểm tra trong lúc sinh (Tiết kiệm bộ nhớ) |
| 3 | O(1) với mỗi query (do dãy Fibonacci nguyên tố rất ngắn) | O(log K) (K là số lượng Fibonacci nguyên tố) | Tối ưu hóa với Precomputation (Khuyến nghị) |
Bài học kinh nghiệm
- Số lượng số Fibonacci nhỏ hơn 10^9 rất ít (khoảng 44 số), nên việc sinh dãy Fibonacci là hoàn toàn khả thi và nhanh chóng.
- Số Fibonacci nguyên tố cực kỳ hiếm. Dưới 10^9, chỉ có 2, 3, 5 là số Fibonacci nguyên tố.
- Kiểm tra số nguyên tố cần tối ưu O(√n) bằng cách chỉ duyệt các số lẻ và tỉa (checking i và i+2), hoặc sử dụng Sieve of Eratosthenes nếu số lượng cần kiểm tra nhỏ.
Lỗi thường gặp
- Quên kiểm tra điều kiện N ≤ x ≤ M khi đếm, dẫn đến đếm nhầm các số Fibonacci nằm ngoài khoảng cho trước.
- Sử dụng biến không đủ lớn (ví dụ dùng int thay vì long long) có thể gây tràn số (overflow) khi tính Fibonacci số thứ 45 trở đi.
- Xử lý sai trường hợp số 1: Số 1 không phải là số nguyên tố, cần loại bỏ khỏi kết quả đếm.
Bình luận