[BOJ][Python] 백준 32454번 - Fibonacci Lucky Numbers

문제 링크: https://www.acmicpc.net/problem/32454

 

---

문제 풀이

피사노 주기, 오일러 피 함수, 분할 정복을 이용한 거듭제곱

 

일단 $7^{7^{7^n}}$을 먼저 보면 벌써부터 답이 없어지는데, 이 수는 매우 크기 때문에 사실상 직접 구하는 것은 불가능하다. 그래서 접근하기가 힘든데, $7^{7^{7^n}}$번째 피보나치 수를 $10$번째 자리까지 출력하라고 적혀있다. 이 말은 피보나치 수를 구했을 때 $10^{10}$으로 나눈 값만 구하면 된다. 그렇다면 여기서 떠올리는 게 있다면 쭉쭉 풀려질 것이다.

 

피사노 주기를 이용하면 된다. 피보나치 수에서 나누는 값이 $10^{m} (m > 2)$라면 주기는 $15 \times 10^{m-1}$다. $m = 10$이므로 주기는 $15 \times 10^{9}$다. 그러면 자연스럽게 $7^{7^{7^n}} (mod\ 15 \times 10^{9})$번째를 구하면 되므로, 우리는 이 값만 구하면 된다. 이 지수 탑을 풀기 위한 잘 알려진 문제가 있지만 이 문제에서는 특별한 조건이 있기 때문에 어렵게 접근하지 않아도 된다.

 

$7^{7^{7^n}} (mod\ 15 \times 10^{9})$에서 오일러 정리를 활용하여 값을 구할 수 있는데 $7$과 $15 \times 10^{9}$은 서로소임을 활용한다.

 

$7^{7^{7^n}}$ $\equiv$ $7^{(7^{7^n}\ mod\ \phi(15 \times 10^{9}))}\ (mod\ 15 \times 10^{9})$

 

$\phi(15 \times 10^{9})$는 $4 \times 10^{8}$이다. 그리고 이 값도 마찬가지로 $7$과 서로소이므로, 여기서도 오일러 정리를 활용한다.

 

$7^{7^n}$ $\equiv$ $7^{(7^n mod\ \phi(4 \times 10^{8}))}\ (mod\ 4 \times 10^{8})$

 

$\phi(4 \times 10^{8})$는 $16 \times 10^{7}$다. 그러면 최종적으로 마지막에 구해야 하는 값이 나온다.

 

$7^{n}\ mod\ 16 \times 10^{7}$

 

이 값을 역순으로 계산하면 $7^{7^{7^n}} (mod\ 15 \times 10^{9})$을 구할 수 있다.

즉, $7^{n}\ mod\ 16 \times 10^{7}$을 구하고 이 값을 $e_{1}$이라 한다.

$7^{e_{1}}\ mod\ 4 \times 10^{8}$을 구한다. 이 값을 $e_{2}$라 한다.

$7^{e_{2}}\ mod\ 15 \times 10^{9}$를 구한다. 이 값을 $e_{3}$이라 하면 $e_{3}$번째의 피보나치 수를 구하면 끝난다.

 

그리고 이 $e_{3}$의 값은 $15 \times 10^{9}$보다 작으므로 피보나치 수를 $O(N)$의 방식으론 느릴 수 있으니 행렬을 이용하여 $O(logN)$으로 구한다.

 

코드