[백준 11778] 피보나치 수와 최대공약수

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

알고리즘 : 수학

난이도 : 플래티넘Ⅴ

 

1. 문제요약

• 1,000,000,000,000,000,000 이하의 두 자연수 n,m이 주어진다.
• n번째 피보나치 수와 m번째 피보나치 수의 최대공약수를 출력한다.
• 다만 숫자가 너무 커지므로 1,000,000,007로 나눈 나머지를 출력한다.

2. 아이디어

• $gcd(F_n,F_m)$을 구하는 문제인데, 이 문제를 풀려면 유클리드 호제법을 알고 있어야 한다.
  유클리드 호제법은 $gcd(x,y) = gcd(x-y,y)$을 의미하는데, 이를 일반화하면 $gcd(x,y) = gcd(y,z)$가 된다. (여기서 z는 x를 y로 나눈 나머지를 의미함)
• 편의상 m이 n보다 크거나 같다고 하고, 문제풀이의 실마리를 얻기위해 $F_n$ 부터 $F_m$까지 나열해보자.
  $F_n$,   $F_{n+1}$,  $F_n+F_{n+1}$,  $F_n+2*F_{n+1}$,  $2*F_n+3*F_{n+1}$,  $3*F_n+5*F_{n+1}$ ...  
• 피보나치수의 특성상 $F_m = F_{m-n-1}*F_n + F_{m-n}*F_{n+1}$이 됨을 알 수 있다. 이는 위 수열에서도 확인할 수 있다.
• 여기에 유클리드 호제법을 적용하면 $gcd(F_n,F_m) = gcd(F_n, F_{m-n}*F_{n+1})$이 된다.
• 연속하는 두 피보나치수는 서로소임을 유클리드 호제법으로 아래처럼 증명할 수 있다.
  $gcd(F_{n+1},F_n) = gcd(F_n, F_{n+1}-F_n) = gcd(F_n,F_{n-1}) = ... =gcd(2,1) = 1$
• 따라서 $gcd(F_n,F_m)=gcd(F_n,F_{m-n}*F_{n+1})=gcd(F_n,F_{m-n})$ 을 얻는다.
• 위 식이 유클리드 호제법과 유사한 형태임에 주목하면, 결국 $gcd(F_n,F_m) = F_{gcd(n,m)}$임을 알 수 있다.
• 결국 피보나치 수를 구하는 문제로 환원되었는데, 이는 앞선 문제 '피보나치 수 6'을 참고하자.

3. 구현과정

• 구현과정은 피보나치 수 6과 거의 동일하다.
• 다만 추가되는 것은 최대공약수를 구하는 함수 gcd(x,y)이다. 이는 유클리드 호제법에 기반하여 재귀적으로 구현하면 된다.

4. 파이썬 코드

# 최대공약수 함수
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

# A*B 함수
def mat_mul(A, B):
    c00 = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % 1000000007
    c01 = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % 1000000007
    c10 = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % 1000000007
    c11 = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % 1000000007
    return [[c00, c01], [c10, c11]]

# A^(2^n) 함수
def mat_pow(A, n):
    for _ in range(n):
        A = mat_mul(A, A)
    return A

# 2의 거듭제곱의 합 변환 함수
def sum_of_bin(x):
    tmp = bin(x)[2:]
    arr = []
    for i in range(len(tmp)):
        if tmp[i] == '1':
            arr.append(len(tmp) - i - 1)
    return arr

n, m = map(int, input().split())
Fibo = [[1, 1], [1, 0]]
ans = [[1, 0], [0, 1]]
target = sum_of_bin(gcd(n, m))
for i in target:
    ans = mat_mul(ans, mat_pow(Fibo, i))
print(ans[1][0])