Tìm UCLN của N số Fibonacci với chỉ số cho trước trong C++

Tìm UCLN của n số Fibonacci tại các chỉ số cho trước. Dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... (chỉ số từ 0). Ví dụ chỉ số {2, 3, 4, 5} → các số {1, 2, 3, 5} → UCLN = 1.

Tính chất: UCLN(Fibo(i), Fibo(j)) = Fibo(UCLN(i, j)). Do đó UCLN của nhiều số Fibonacci = Fibo(UCLN của các chỉ số).

Ví dụ

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

Kết quả

GCD of fibo terms using indices: 2