Hiểu bài toán

Cho hai số nguyên dương n và m (n ≤ m). Yêu cầu đếm số lượng số Fibonacci nằm trong khoảng [n, m] là số nguyên tố.

Số Fibonacci được định nghĩa:

• F(0) = 0
• F(1) = 1
• F(k) = F(k-1) + F(k-2) với k ≥ 2.

Ta cần tìm các số Fibonacci F(i) sao cho n ≤ F(i) ≤ m và F(i) là số nguyên tố.

Lưu ý:

• Các số Fibonacci tăng rất nhanh.
• Ví dụ: Dãy số Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó.

Các cách tiếp cận

Cách Brute Force (Sinh dãy Fibonacci và Kiểm tra)

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

// Hàm kiểm tra số nguyên tố (Optimized Trial Division)
bool isPrime(long long n) {
    if (n < 2) return false;
    if (n == 2 || 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() {
    ifstream fin("fibo.INP");
    ofstream fout("fibo.OUT");

    long long n, m;
    fin >> n >> m;

    int count = 0;
    long long a = 0, b = 1;

    // F(0) = 0 (Không phải số nguyên tố)
    // F(1) = 1 (Không phải số nguyên tố)
    // Bắt đầu sinh từ F(2) trở đi

    // Sử dụng biến phụ để tránh tràn số khi cập nhật
    // Duyệt trong khoảng [n, m]
    while (a <= m) {
        if (a >= n) {
            if (isPrime(a)) {
                count++;
            }
        }
        long long next = a + b;
        a = b;
        b = next;
    }

    fout << count << endl;
    return 0;
}

• Time Complexity: O(K * sqrt(M)) với K là số lượng số Fibonacci trong khoảng [0, M]. K rất nhỏ (nhỏ hơn 100 với M <= 10^18).
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất:

1. Sinh ra các số Fibonacci theo quy luật F(i) = F(i-1) + F(i-2).
2. Với mỗi số Fibonacci sinh ra, kiểm tra xem nó có nằm trong khoảng [n, m] không.
3. Nếu có, kiểm tra nó có phải là số nguyên tố không.
4. Cách này hiệu quả vì số Fibonacci tăng rất nhanh, số lượng số Fibonacci cần xét rất ít.

Cách Tối ưu hóa sinh dãy (Xử lý biên)

#include <bits/stdc++.h>
using namespace std;

bool isPrime(long long x) {
    if (x < 2) return false;
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main() {
    ifstream fin("FIBO.INP");
    ofstream fout("FIBO.OUT");

    long long n, m;
    fin >> n >> m;

    int count = 0;
    long long a = 1, b = 1;

    // Xử lý riêng F(1) = 1 (không phải số nguyên tố)
    // Xử lý riêng F(2) = 1 (không phải số nguyên tố)
    // Bắt đầu tính từ F(3) = 2

    // Tuy nhiên, đoạn code mẫu trong solution 3 có vẻ chưa tối ưu hoàn toàn logic
    // Dưới đây là phiên bản logic chuẩn hóa:

    // Giả sử ta cần đếm các số Fibonacci >= n
    // F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, ...

    long long f0 = 0;
    long long f1 = 1;

    // Kiểm tra F(0)
    if (f0 >= n && f0 <= m && isPrime(f0)) count++; 

    // Kiểm tra F(1)
    if (f1 >= n && f1 <= m && isPrime(f1)) count++;

    while (true) {
        long long f2 = f0 + f1;
        if (f2 > m) break;

        if (f2 >= n && isPrime(f2)) count++;

        f0 = f1;
        f1 = f2;
    }

    fout << count << "\n";
    return 0;
}

• Time Complexity: Tương tự Approach 1
• Space Complexity: O(1)

Đây là biến thể của Approach 1.

1. Thay vì dùng vòng lặp while để sinh số Fibonacci, ta dùng biến.
2. Cần lưu ý các số Fibonacci đầu tiên: 0, 1, 1.
3. Các số 0 và 1 không phải là số nguyên tố.
4. Ta bắt đầu sinh từ số Fibonacci thứ 2 (giá trị 1) hoặc thứ 3 (giá trị 2).
5. Ưu điểm của Approach 1 (vòng lặp sinh từ 0, 1) là code ngắn gọn và dễ xử lý chung cho mọi trường hợp hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Số Fibonacci tăng rất nhanh (theo cấp số nhân với hệ số vàng ~1.618). Do đó, số lượng số Fibonacci trong một khoảng giá trị [n, m] (kể cả khi m rất lớn, ví dụ 10^18) là rất nhỏ (chỉ khoảng 80-90 số).
• Bài toán có thể giải quyết bằng cách sinh tuyến tính các số Fibonacci và kiểm tra tính nguyên tố cho mỗi số.
• Hàm kiểm tra số nguyên tố cần tối ưu (chia hết cho 2, 3, rồi chỉ kiểm tra các số 6k±1) để đảm bảo tốc độ.

Lỗi thường gặp

• Sai quy tắc tính Fibonacci: F(0) = 0, F(1) = 1. Đừng quên F(0).
• Tràn số (Overflow): Nếu sinh Fibonacci quá nhanh hoặc dùng biến sai loại (ví dụ int thay vì long long), có thể tràn số. May mắn là số Fibonacci đạt 10^18 khá nhanh nên vòng lặp sẽ dừng sớm.
• Xử lý số 1: Số 1 không phải là số nguyên tố. Cần chắc chắn logic kiểm tra isPrime trả về false cho số 1.
• Độ lớn của n và m: Có thể lên tới 10^18, bắt buộc phải dùng long long (hoặc unsigned long long).