BOJ 11778 피보나치 수와 최대공약수

www.acmicpc.net/problem/11778

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

피보나치 문제들을 풀면서 비슷한 유형들 여러 가지를 푸는데 상당히 재미있다.

이번 문제는 행렬 제곱을 이용한 큰 수의 피보나치 수를 구해서 최대공약수를 구하는 것이다.

이 문제는 각각 n과 m에 대해서 피보나치 수열을 구하고 그 수의 최대 공약수를 구해도 되지만 n과 m을

미리 최대공약수를 구한 뒤 그 수의 피보나치 수를 구해도 된다.

#include <iostream>
#include <vector>
using namespace std;
using ll = unsigned long long;
const int MOD = 1e9 + 7;
#define vii vector<vector<ll>>
#define vi vector<ll>

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

vii operator* (const vii& a, const vii& b) {
	ll sz = a.size();
	vii ret(sz, vi(sz));
	for (ll i = 0; i < sz; i++) {
		for (ll j = 0; j < sz; j++) {
			for (ll k = 0; k < sz; k++) {
				ret[i][j] += a[i][k] * b[k][j];
			}
			ret[i][j] %= MOD;
		}
	}
	return ret;
}

vii power(vii& a, ll b) {
	ll sz = a.size();
	vii ret(sz, vi(sz));
	for (ll i = 0; i < sz; i++) ret[i][i] = 1;

	while (b) {
		if (b % 2) ret = ret * a;
		b /= 2;
		a = a * a;
	}
	return ret;
}

int main() {
	ll n, m;
	cin >> n >> m;
	ll GCD = gcd(n, m);
	vii A = { {1,1},{1,0} };
	vii ans = power(A, GCD);
	cout << ans[0][1] << endl;

	return 0;
}

왜인지 증명은 못하겠다. 처음에는 n과 m에 대해서 피보나치 수를 구한 뒤에 최대공약수를 구하려 해서 8번은 틀린 것 같다.