[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}}(mod15\times {10}^9)$번째를 구하면 되므로, 우리는 이 값만 구하면 된다. 이 지수 탑을 풀기 위한 잘 알려진 문제가 있지만 이 문제에서는 특별한 조건이 있기 때문에 어렵게 접근하지 않아도 된다.

 

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

 

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

 

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

 

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

 

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

 

$7^{n}mod16\times {10}^7$

 

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

즉, $7^{n}mod16\times {10}^7$을 구하고 이 값을 $e_1$이라 한다.

$7^{e_1}mod4\times {10}^8$을 구한다. 이 값을 $e_2$라 한다.

$7^{e_2}mod15\times {10}^9$를 구한다. 이 값을 $e_3$이라 하면 $e_3$번째의 피보나치 수를 구하면 끝난다.

 

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

 

코드

	import sys
	input = sys.stdin.readline
	mod = int(1e10)
	def calc(m1, m2):
	matrix = [[0 for _ in range(2)] for _ in range(2)]
	for i in range(2):
	for j in range(2):
	for k in range(2):
	matrix[i][j] += m1[i][k] * m2[k][j]
	matrix[i][j] %= mod
	return matrix
	def func(mat, n):
	if n == 1:
	return mat
	else:
	if n % 2 == 0:
	new = func(mat, n//2)
	return calc(new, new)
	else:
	return calc(func(mat, n-1), mat)
	for _ in range(int(input())):
	n = int(input())
	matrix = [[1, 1], [1, 0]]
	e1 = pow(7, n, 16*int(1e7))
	e2 = pow(7, e1, 4*int(1e8))
	e3 = pow(7, e2, 15*int(1e9))
	if e3 <= 1: rans = '0'*9+str(e3)
	else: rans = str((func(matrix, e3-1)[0][0])%mod).zfill(10)
	print(rans)

view raw 32454.py hosted with ❤ by GitHub