【C++】指定されたインデックスのN個のフィボナッチ数のGCDを効率的に求める方法

本記事では、指定された複数のインデックスに対応するN個のフィボナッチ数の最大公約数（GCD）を、C++で効率的に求める方法を解説します。

フィボナッチ数列と問題の概要

まずおさらいとして、フィボナッチ数列は「0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …」のように、直前の2つの項の和によって定義される数列です。インデックスは0から始まるため、0番目の要素は0、1番目の要素は1となります。

例えば、インデックス{2, 3, 4, 5}に対応するフィボナッチ数は{1, 2, 3, 5}であり、これらのGCDは1です。

鍵となる性質：GCD(Fibo(i), Fibo(j)) = Fibo(GCD(i, j))

この問題を解くうえで非常に強力なのが、フィボナッチ数列が持つ次の美しい数学的性質です。

GCD(Fibo(i), Fibo(j)) = Fibo(GCD(i, j))

つまり、「i番目のフィボナッチ数とj番目のフィボナッチ数のGCD」は、「iとjのGCDをインデックスとするフィボナッチ数」と等しくなります。この性質を利用すれば、巨大なフィボナッチ数同士のGCDを直接計算する必要はありません。まずインデックス同士のGCDを求め、その値に対応するフィボナッチ数を1つだけ計算すればよいため、計算量を大幅に抑えられます。

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;
int getFiboTerm(int n){
    int fibo[n + 2];
    fibo[0] = 0; fibo[1] = 1;
    for(int i = 2; i<= n; i++){
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    return fibo[n];
}
int getNFiboGCD(int arr[], int n){
    int gcd = 0;
    for(int i = 0; i < n; i++){
        gcd = __gcd(gcd, arr[i]);
    }
    return getFiboTerm(gcd);
}
int main() {
    int indices[] = {3, 6, 9};
    int n = sizeof(indices)/sizeof(indices[0]);
    cout << "GCD of fibo terms using indices: " <<
    getNFiboGCD(indices, n);
}

コードの解説

• getFiboTerm関数：動的計画法を用いて、n番目のフィボナッチ数を計算して返します。
• getNFiboGCD関数：配列内のすべてのインデックスに対して__gcd関数でGCDを順に求め、最終的に得られたGCDに対応するフィボナッチ数を返します。
• main関数：インデックスの配列{3, 6, 9}を渡し、結果を出力します。

実行結果

GCD of fibo terms using indices: 2

結果の検証

インデックス{3, 6, 9}の場合、まずGCD(3, 6, 9) = 3を求めます。次に、3番目のフィボナッチ数Fibo(3) = 2を計算します。実際に各フィボナッチ数を確認すると、Fibo(3) = 2、Fibo(6) = 8、Fibo(9) = 34であり、GCD(2, 8, 34) = 2となるため、上記の性質どおりの正しい結果が得られていることがわかります。