[BOJ] 11778 : 피보나치 수와 최대공약수 - travelbeeee

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

---

[알고리즘풀이]

먼저, 피보나치에 관한 수학적 정리를 이용해야 문제를 해결할 수 있습니다.

gcd(a,b) = g 라고 했을 때, gcd( fibonacci(a), fibonacci(b) ) = fibonacci(g) 이다.

즉, a번 째 피보나치 수와 b번 째 피보나치 수의 최대공약수는 a, b의 최대공약수번 째 피보나치 수와 같습니다.

이 정리를 이용해, 우리는 fibonacci(gcd(a,b)) 를 구하면 됩니다.

gcd(a,b) 는 유클리드 호제법을 이용해서 빠르게 구할 수 있고,

fibonacci(gcd(a,b))는 행렬의 곱셈을 이용해서 문제를 해결할 수 있습니다.

( 유사 문제 풀이 : https://travelbeeee.tistory.com/92?category=817856 )

#include<iostream>

#define m 1000000007
#define ll long long

using namespace std;

ll a,b, fib_n, fib_m, ta, tb;

ll gcd(ll a, ll b) {
	if (b > a) {
		ll t = a;
		a = b;
		b = t;
	}
	while (b) {
		ll r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> a >> b;
	ll GCD = gcd(a, b);

	ll M[2][2] = { {1,1},{1,0} };
	ll A[2][2] = { {1,0},{0,1} };
	ta = GCD - 1;
	while (ta) {
		if (ta % 2 == 1) {
			// A * M 을 A에 갱신.
			ll temp[2][2] = {};
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					// A[i][j] = A[i][j] * M[i][j];
					for (int k = 0; k < 2; k++) {
						temp[i][j] += ( M[i][k] * A[k][j] ) % m;
					}
				}
			}
			for (int i = 0; i < 2; i++)
				for (int j = 0; j < 2; j++)
					A[i][j] = temp[i][j];
		}
		// M * M을 갱신.
		ll temp[2][2] = {};
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				// M[i][j] = M[i][j] * M[i][j];
				for (int k = 0; k < 2; k++) {
					temp[i][j] += (M[i][k] * M[k][j]) % m;
				}
			}
		}
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				M[i][j] = temp[i][j];
		ta /= 2;
	}
	cout << A[0][0] % m;
}

---