11778번

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

이 문제는 처음에 피보나치 수를 각각 구하고, 유클리드 호제법을 이용하려 했으나 실패.

일단 범위가 너무 크기 때문에, 피보나치 수를 구할 수 없었다.

그래서 차선책으로 피보나치 수의 나머지를 구하고, 그 값을 유클리드 호제법을 이용했으나...

(a%m, b%m)의 최대공약수와 (a, b의 최대공약수)%m은 다르므로.. 이는 성립할리가 없었다.

그래서 피보나치의 성질 중 하나인

GCD(F[N],F[M])=F[GCD(N,M)] 을 사용할 수밖에 없었다.

이를 이용하면 굉장히 편하게 풀린다.

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
const long long mod = 1000000007;
typedef vector<vector<long long>> matrix;
matrix operator *(matrix &A, matrix &B)
{
    matrix ret(2, vector<long long>(2));
 
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            long long sum = 0;
            for (int m = 0; m < 2; m++)
            {
                sum += ((A[i][m]%mod) * (B[m][j] % mod)) % mod;
            }
            ret[i][j] = sum%mod;
        }
    }
 
    return ret;
 
}
matrix calc(matrix &A, long long B)
{
    if (B == 0)
    {
        matrix ret(2, vector<long long>(2));
        ret[0][0] = 1, ret[0][1] = 0, ret[1][0] = 0, ret[1][1] = 1;
        return ret;
    }
    else if (B % 2 == 0)
    {
        matrix temp = calc(A, B / 2);
        return temp*temp;
    }
    else
    {
        matrix temp = calc(A, B - 1);
        return A*temp;
    }
 
}
long long gcd(long long a, long long b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a%b);
    }
}
int main()
{
    long long n, m;
    scanf("%lld %lld", &n, &m);
    matrix F(2, vector <long long>(2));
    F[0][0] = 1, F[0][1] = 1, F[1][0] = 1, F[1][1] = 0;
    long long a = gcd(n, m);
    
 
    printf("%lld\n", calc(F,a)[0][1] %mod);
 
    return 0;
}