백준-2749-피보나치 수 3

피보나치 수열을 구하는 여러 방법 중 하나

피사노 주기를 이용하는 방법을 기억하자

문제

피보나치 수 3 (https://www.acmicpc.net/problem/2749)

풀이

1. 문제조건 해석

   피보나치 수를 1,000,000으로 나눈 나머지를 구하는 문제이다.

2. 알고리즘

   • 파사노 주기를 이용한다.

     피보나치 수를 나눈 수는 항상 주기를 가진다.

     피보나치 수를 나눌 수를 $k$라고 할 때, $k=10^n$ 이면,

     피사노 주기는 $15∗10^{n−1}$이다

   • 1,000,000으로 나눈 나머지를 구하는 문제이므로

     파사노 주기는 $15*10^{6-1}$ 이다.

3. 코드

n = int(input())

def fibo3(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b%1000000, (a+b)%1000000

    return a 

print(fibo3(n%(15*(10**5))))