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

처음에는 입력받은 두 값의 피보나치 수를 구하고 최대공약수를 구했는데 계속 틀렸다고 나왔다.

 

-> (N%mod, M%mod)의 최대공약수와 (N,M의 최대공약수)%mod가 다르기 때문이라고 한다.

 

찾아보니 다들 피보나치 성질 중 G{fibo(N),fibo(M)} = fibo{G(N,M)} 이 성질을 이용해서 먼저 최대공약수를 구하고 피보나치 수를 구했다.