[백준 11778] 피보나치 수와 최대공약수 [C]

백준 - 11778

---

풀이

n, m번째 피보나치 수의 최대공약수는, gcd(n, m)번째 피보나치 수와 같다.

구글에 영어로 검색하니 바로뜬다... 이 무슨 

"백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다.

---

소스코드

#include <stdio.h>
#define ll long long
const int MOD = 1e9+7;
ll X[2][2] = {0, 1, 1, 1};

ll gcd(ll a, ll b){
    return b ? gcd(b, a%b) : a;
}
void fibo(ll result[][2], ll f[][2]){
    int temp[2][2] = {0,};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                temp[i][j] += (result[i][k]*f[k][j]) %MOD;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            result[i][j] = temp[i][j] %MOD;	
}
int main(){
    ll n, m, result[2][2] = {1, 0, 0, 1};
    scanf("%lld %lld", &n, &m);
    n = gcd(n, m);
	
    while (n){
        if (n & 1) fibo(result, X);
        fibo(X, X);
        n >>= 1;
    }
    printf("%lld", result[1][0]);
}

---

출처 및 참고자료

11778번: 피보나치 수와 최대공약수

GCD of Fibonacci Numbers

[백준 11444] 피보나치 수 6 [C]