[백준 11778번] 피보나치 수와 최대공약수 (Python3)

import math
mod = 10**9+7

memo = {1:1,2:1,3:2,4:3,5:5}

def Fibo(n):
  if memo.get(n):
    return memo[n]
  else:
    if n%2 == 1:
      memo[n] = (Fibo(n//2)**2+Fibo(n//2+1)**2)%mod
    else:
      memo[n] = (Fibo(n+1)-Fibo(n-1))%mod
    return memo[n]

N,M = map(int,input().split())
print(Fibo(math.gcd(N,M)))

피보나치 수 응용문제

피보나치 수 구하는 코드는 [백준 11444번] 피보나치 수 6 (Python3) (tistory.com) 를 재탕하였다.

 

처음에는 그냥 Fibo(N),Fibo(M)의 gcd를 구하면 된다고 생각했다. 그러나 mod연산 때문에 성립하지 않는다는 것을 알게되었다. 그러다가 예제를 봤는데, 예제의 16,24번째 피보나치 수의 최대공약수가 21인데, 이 수가 곧 8번째 피보나치 수였다. 그래서 혹시 gcd(Fibo(N),Fibo(M)) = Fibo(gcd(N,M)) 인가? 하고 제출해봤더니 맞았다.

 

위의 수식이 왜 성립하는 지에 대한 증명은 유클리드 호제법의 원리를 이용한다. (참고 피보나치수의 최대공약수 (mono-cake.coffee))

 

 

오늘의 교훈) 피보나치 수는 정말 다양한 규칙을 가지고있다.