취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11238번 문제인 Fibo이다.
문제는 아래 링크를 확인하자.

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

초항과 두번째 항이 각각 1인 피보나치수열에 대하여 피보나치수열의 x번째 항과 y번째 항의 gcd는 피보나치수열의 gcd(x,y)번째 항과 같다는 성질을 이용하여 문제를 해결하자.

또한, 점화식을 빠르게 계산하기 위해 binary exponentiation을 이용하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		int x, y; cin >> x >> y;
		int gcdxy = gcd(x, y);
		ll mat[2][2] = {{1,1},{1,0}};
		ll vec[2] = { 1,0 };
		
		while (gcdxy > 0) {
			if (gcdxy & 1) {
				ll temp = (mat[0][0] * vec[0] + mat[0][1] * vec[1])%1000000007;
				vec[1] = (mat[1][0] * vec[0] + mat[1][1] * vec[1])%1000000007;
				vec[0] = temp;
			}
			ll mat00 = (mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0]) % 1000000007;
			ll mat01 = (mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]) % 1000000007;
			ll mat10 = (mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0]) % 1000000007;
			ll mat11 = (mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]) % 1000000007;
			mat[0][0] = mat00, mat[0][1] = mat01, mat[1][0] = mat10, mat[1][1] = mat11;
			
			gcdxy >>= 1;
		}

		cout << vec[1] << '\n';
	}
}