C++でN番目のフィボナッチ数の下2桁を求めるプログラム

この記事では、数値Nが与えられたときに、N番目のフィボナッチ数の下2桁（最下位2桁）を求めるC++プログラムを紹介します。

問題の概要

N番目のフィボナッチ数について、その下2桁を求めるのが課題です。具体的な例を見てみましょう。

入力：N = 120
出力：81

解法のアプローチ

最も単純な方法は、フィボナッチ数の一般式（ビネの公式）を使ってN番目の項を直接計算することです。しかし、Nが非常に大きい数になると、この方法はオーバーフローや精度の問題で現実的ではありません。

そこで役立つのが、フィボナッチ数列の重要な性質です。フィボナッチ数の下2桁は300項ごとに同じ並びが繰り返されるというものです。これは「ピザーノ周期」と呼ばれる性質の一つで、例えば第75項の下2桁と第975項の下2桁は一致します。

つまり、最初の300項まで計算すればすべてのパターンが網羅できるため、Nを300で割った余りに対応する項を計算すればよいことになります。これにより、Nがどれほど巨大でも高速に答えを求められます。

サンプルコード

#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;
}

実行結果

The last two digits of 683th Fibonacci term are 97

コードの解説

関数findLastTwoDigitNtermでは、まずNを300で割った余りに置き換えることで、計算すべき項を300以下に抑えています。その後、関数fiboで反復計算によりフィボナッチ数を求め、100で割った余りを取ることで下2桁だけを取り出しています。

なお、Nが1以下の場合はループが一度も実行されず未初期化の値を返す可能性があるため、実用的にはfibo関数内でN≤1の場合にNをそのまま返すガード処理を追加するとより安全です。

まとめ

フィボナッチ数列の下2桁が300項で一巡する性質を利用すれば、Nがどんなに大きくても最大300回程度の反復計算で答えを得られます。このような周期性の活用は、競技プログラミングなどで大きな数の特定の桁を扱う際によく使われるテクニックなので、ぜひ覚えておきましょう。