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

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

gcd(F_n, F_m) = F_gcd(n, m)입니다. 증명은 귀납법으로 할 수 있습니다. ( https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml )

그러면 주어진 n, m에 대해 F_n, F_m을 구할 필요 없이 F_gcd(n, m)을 구하면 되고, n과 m이 매우 큰 만큼 행렬의 거듭제곱을 이용해 F_a를 O(log a)로 구해야 시간 내로 답을 얻을 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/11778.cpp