[BOJ 10908] Phibonacci

피보나치 수열 $F$와 황금비 $\phi$, 음이 아닌 자연수 $n,k$에 대해 어떤 정수 $A,B$가 아래 식을 만족할 때 $A,B$를 구하는 것이 우리의 목표에요!

$(F_{n}\phi+F_{n-1})^{k}=A\phi^{k}+B$

우린 한가지 성질을 알고 가야 하죠!

$\phi^{n}=F_{n}\phi+F_{n-1}$

이를 증명해봅시다.

 

• $\phi^{n}=F_{n}\phi+F_{n-1}$

<증명>

$n=1$일 때 

$\phi=F_{1}\phi=\phi$

로 성립하네요.

$n=2$일 때

$\phi^{2}=F_{2}\phi+F_{1}=\phi+1$ $\cdot\cdot\cdot *$

$\phi$는 방정식  $x^{2}=x+1$의 한 근이므로 위 식 역시 성립해요.

$n=k$일 때 

$\phi^{k}=F_{k}\phi+F_{k-1}$

이 성립한다고 하고

양 변에 $\phi$를 곱합시다.

$\phi^{k+1}=F_{k}\phi^{2}+F_{k-1}\phi$

$*$에 의하여

$\phi^{k+1}=F_{k}\phi+F_{k}+F_{k-1}\phi=F_{k+1}\phi+F_{k}$

$n=k+1$일 때도 성립해요!

따라서 수학적 귀납법에 의해 다음 식이 성립합니다.

$\therefore \phi^{n}=F_{n}\phi+F_{n-1}$

 

위 성질을 이용해 식을 변형해봅시다.

$(F_{n}\phi+F_{n-1})^{k}=\phi^{nk}=F_{nk}\phi+F_{nk-1}=A\phi^{k}+B$

$\phi^{k}=F_{k}\phi+F_{k-1}$이므로

$F_{nk}\phi+F_{nk-1}=AF_{k}\phi+B+AF_{k-1}$

$\phi$는 무리수이므로 항등조건에 의해

$AF_{k}=F_{nk}$,  $A=\frac{F_{nk}}{F_{k}}$

$F_{nk-1}=B+AF_{k-1}$,  $B=F_{nk-1}-AF_{k-1}$

 

문제에서 $A, B$가 존재하지 않으면 -1을 출력하라고 써있습니다.

$A$가 존재하지 않는 경우만 살펴보면 됩니다. $\frac{F_{nk}}{F_{k}}$가 정수가 아닐때를 살펴보면 되는데 사실 이 식은 정수가 될 수밖에 없습니다! 증명해보죠!

 

• $\frac{F_{nk}}{F_{k}}$는 정수이다.

<증명>

$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}$라고 말할 수 있죠!

 

위 성질이 성립하니 $A, B$는 반드시 존재합니다.

그럼 계산만 해주면 다 끝이네요! $A$만 계산하면 $B$는 간단합니다.

$A$가 분수인데 어떻게 계산할까요? 모듈러 역원을 이용하는 것입니다. 문제에서 주어진 수 $1000000007$는 소수이기 때문에 페르마의 소정리를 이용해 역원을 쉽게 구할 수 있습니다. 그 방법은 다음과 같습니다.

소수 $p$, 그와 서로소인 정수 $a$가 아래 식을 만족합니다.

$a^{p-1} \equiv 1 \pmod{p}$

이를 이용하면 아래와 같은 분수 꼴을 계산할 수 있습니다.

$\frac{1}{a} \equiv a^{p-2} \pmod{p}$

하지만 이 조건은 너무 가혹합니다. $a$와 $p$가 서로소이기 떄문입니다.

서로소가 아닐 떄, 계산하는 아이디어는 $\pmod{p^{2}}$을 이용하는 것입니다.

$\frac{a}{b} \pmod{p^{2}}$

을 계산한다고 합시다. (문제 조건에서 $a$는 $b$의 배수이기 때문에 $a=nb$로 가정하겠습니다.)

먼저 $a,b$에 대해 $\pmod{p^{2}}$을 계산하겠죠! 그럼 아래와 같이 표현해봅시다.

$a=p^{2}q_{a}+r_{a}$

$b=p^{2}q_{b}+r_{b}$

만약 $p \nmid r_{b}$라면 아래 식이 성립하기 때문에 $\pmod{p}$로 계산하면 됩니다.

(몫은 $a,b$둘다 다르지만 편의상 $q$로 표시합니다.)

$a=pq+(r_{a} \pmod{p})$

$b=pq+(r_{b} \pmod{p})$

만약 $p \mid r_{b}$라면

$p | r_{b},\ p | r_{a}$가 됩니다. 어차피 우리는 $a/b$를 계산하니까 $a,b$ 각각을 $p$로 나누면 되겠죠?

$a^{\prime}=pq+r_{a}^{\prime}$

$b^{\prime}=pq+r_{b}^{\prime}$

이때 $0 \le r_{a},\ r_{b} < p^{2}$이므로 $0 \le r_{\prime},\ r_{\prime} < p$입니다.

만약 $r_{b}=0$이라면 더 귀찮아지겠지만 위 문제 조건에서는 저 케이스가 존재하지 않는 것 같습니다!

 

귀찮은 일

$r_{b}=0$인 경우 저런 경우가 나오지 않을 때 까지 $p^{n}$의 지수를 증가시켜 나머지를 구하고 계속 $p$로 나누어주며 $p^{n}$을 $p$로 만들어주면 됩니다. 

 

그렇기 때문에 우리는 $a^{\prime}/b^{\prime} \pmod{p}$로 편하게 계산할 수 있죠.

 

이 전체 과정을 구현한 것이 아래에 있습니다. $n, k \le 10^{12}$라서 $nk \le 10^{24}$가 되므로 long long int를 넘어갑니다. 힘든 일이 발생하지 않도록 Python 3으로 구현했습니다.

 

코드 보기

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 fpow(n,k):
    s=1
    while k:
        if k&1:
            s=s*n%p
        n=n*n%p
        k>>=1
    return s
 
p=int(1e9+7)
p_=p*p
n,k=map(int,input().split())
f_nk=fibo(n*k)
f_k=fibo(k)
if f_k%p==0:
    f_k//=p
    f_nk//=p
A=f_nk*fpow(f_k,p-2)%p
B=(fibo(n*k-1)-A*fibo(k-1))%p
print(A,B)