2021. 8. 21. 12:53ㆍPS/백준
피보나치 수열 $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으로 구현했습니다.
# 코드 보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
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)
|
cs |
# 닫기
'PS > 백준' 카테고리의 다른 글
[BOJ 1770] 배수와 약수의 개수 (7) | 2021.08.21 |
---|---|
[BOJ 11778] 피보나치 수와 최대공약수 (1) | 2021.08.21 |
[BOJ 19577] 수학은 재밌어 (0) | 2021.08.16 |
[BOJ 13430] 합 구하기 (2) | 2021.08.15 |
[BOJ 4798] 등차수열에 관한 디리클레의 정리 (1) | 2021.06.02 |