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

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

https://www.acmicpc.net/problem/11778

문제

• n 번째 피보나치 수와 m 번째 피보나치 수의 최대공약수를 구해보자.

입력

• n과 m

• n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수 

출력

• n 번째 피보나치 수와 m 번째 피보나치 수의 최대공약수를 1,000,000,007으로 나눈 나머지

접근

• 최대공약수는 유클리드 호제법으로 구한다.

  • GCD(a, b) = GCD(b, a % b)

• 피보나치 수는 수가 매우 크기 때문에 DP로 구하면 시간초과

• 행렬 곱셈을 활용하여 O(log N)의 시간복잡도로 피보나치 수를 구해야한다.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
typedef vector<vector<ull>> matrix;
const ull MOD = 1000000007;
​
//유클리드 호제법 GCD
ull gcd(ull a, ull b)
{
    if (b == 0) return a;
​
    return gcd(b, a%b);
}
​
//2x2 행렬 곱셈
matrix operator*(matrix &a, matrix &b)
{
    ull x = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    ull y = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    ull z = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    ull w = a[1][0] * b[0][1] + a[1][1] * b[1][1];
​
    x %= MOD;
    y %= MOD;
    z %= MOD;
    w %= MOD;
​
    matrix ret = { { x,y },{ z,w } };
    return ret;
}
​
//행렬 제곱
void power(matrix &F, ull n)
{
    if (n <= 1) return;
​
    matrix E = { { 1, 1 },{ 1, 0 } };
    power(F, n / 2);
    F = F * F;
    if (n % 2 != 0) {
        F = F * E;
    }
}
​
//행렬을 이용한 피보나치 수열 구하기
ull fib(ull n)
{
    matrix F = { { 1, 1 },{ 1, 0 } };
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}
​
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
​
    ull n, m;
    cin >> n >> m;
​
    ull ngcd = gcd(n, m);
    cout << fib(ngcd) % MOD;
​
    return 0;
}