หาหลักสองหลักสุดท้ายของพจน์ฟีโบนัชชีที่ N ใน C++

หาหลักสองหลักสุดท้าย (LSBs) ของพจน์ฟีโบนัชชีที่ N

ตัวอย่าง: N = 120 → 81

วิธีแก้ปัญหา (Pisano Period)

หลักสองหลักสุดท้ายของฟีโบนัชชีซ้ำทุก 300 พจน์ (Pisano period mod 100 = 300)

ดังนั้นคำนวณเฉพาะ N mod 300 แล้วหา mod 100

ตัวอย่างโค้ด 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 = 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;
}

Output

The last two digits of 683th Fibonacci term are 97