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

우리가 이용할 식은 아래와 같습니다.

$\gcd(f_{n},f_{m})=f_{\gcd(n,m)}$

위 성질을 증명해봅시다.

• $\gcd(f_{k+1},f_{k})$

$\gcd(f_{k+1},f_{k})=\gcd(f_{k},f_{k-1})=\gcd(f_{k-1},f_{k-2})=...=\gcd(f_{2},f_{1})=1$

 

• $f_{k} | f_{nk}$

$n=1$일 때 $f_{k} | f_{k}$임은 자명합니다.

$n=a$일 떄 $f_{k} | f_{ak}$라고 가정합시다.

$f_{(a+1)k}=f_{ak}f_{k-1}+f_{ak+1}f_{k}$

그럼 이때! 가정에 의해 $f_{k} | f_{(a+1)k}$가 성립합니다!

따라서 수학적 귀납법에 의해 $f_{k} | f_{nk}$라고 말할 수 있죠!

• $\gcd(f_{k},f_{nk+1})=1$

$\gcd(f_{nk},f_{nk+1})=1$입니다. 그런데! $f_{k} | f_{nk}$이므로 $\gcd(f_{k},f_{nk+1})=1$

• $\gcd(f_{n},f_{m})=f_{\gcd(n,m)}$

$n=mk+r$이라고 합시다.

$f_{n}=f_{mk}f_{r-1}+f_{mk+1}f_{r}$

$\gcd(f_{n},f_{m})=\gcd(f_{m},f_{n} \pmod{f_{m}})$

성질 2번에 의해

$f_{n} \equiv f_{mk+1}f_{r} \pmod{f_{m}}$

$\gcd(f_{m},f_{mk+1}f_{r})$

이때 성질 3번에 의해

$=\gcd(f_{m},f_{r})$

$\therefore \gcd(f_{n},f_{m})=\gcd(f_{m},f_{r})$

이는 정수 $n,m$에 대하여 $\gcd$를 계산했을 때와 똑같은 형상입니다!

$\therefore \gcd(f_{n},f_{m})=f_{\gcd(n,m)}$

 

우리가 계산해야 하는 것은 $f_{\gcd(n,m)}$입니다.

이를 구현한 코드는 아래에 있습니다.

 

코드 보기

def mul_mat(s,t):
    he=[[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            q=0
            for l in range(2):
                q+=s[i][l]*t[l][j]%p
            he[i][j]=q%p
    return he
 
 
def fibo(n):
    if n<=1:
        return abs(n)
    n-=2
    s=[[1,1],[1,0]]
    t=[[1,1],[1,0]]
    while n:
        if n&1:
            t=mul_mat(t,s)
        s=mul_mat(s,s)
        n>>=1
    return t[0][0]
 
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
 
p=int(1e9+7)
n,m=map(int,input().split())
print(fibo(gcd(n,m)))