Tìm 2 chữ số cuối của số Fibonacci thứ N trong C++

Tìm 2 chữ số cuối (mod 100) của số Fibonacci thứ N.

Tối ưu chu kỳ Pisano

2 chữ số cuối lặp lại chu kỳ 300. Tính N % 300 rồi tính Fibonacci modulo 100.

Mã nguồn C++

#include <iostream>
using namespace std;

long int fibo(int N) {
    long int a=0, b=1, c;
    for (int i=2; i<=N; i++) { c=a+b; a=b; b=c; }
    return c;
}

int findLastTwoDigitNterm(int N) {
    N %= 300;
    return fibo(N) % 100;
}

int main() {
    int N = 683;
    cout << "The last two digits of " << N << "th Fibonacci term are " << findLastTwoDigitNterm(N);
    return 0;
}

Đầu ra

The last two digits of 683th Fibonacci term are 97