피사노 주기를 이용한 피보나치 수열 해법

1. 피사노 주기

 

피보나치 수열을 자연수 n으로 나눈 나머지가 일정한 주기를 이룬다는 것을 1960년 IBM의 한 직원이 증명했다

 

 

 

예를 들어 0,1로 시작하는 피보나치 수열을 3으로 나눈 나머지는 위와 같이 0,1,1,2,0,2,2,1이 반복된다는 것을 알 수 있다

 

 

2. 연습문제

 

9471번: 피사노 주기 (acmicpc.net)

9471번: 피사노 주기

 

추가로 몇가지 성질이 있다고 제시해주는데

 

 

어쨌든 이 문제는 피보나치 수열을 자연수 m으로 나눈 나머지가 주기를 이룬다는 사실을 알고 코딩을 해서 

 

반복되는 수열의 길이를 구해야하는 문제

 

 

3. 풀이

 

핵심은 피보나치 수열 처음이 0,1부터 시작하니까 첫 항을 0,1로 초기화하고,

 

다음 항을 계속 구하면서

 

최초로 0,1이 언제 돌아오는지 계산하면 된다

 

어떻게 코딩하는 방법은 여러가지 있겠지만... 조심해야할 점은 period값 실수하기 쉽다

 

처음 period=1로 잡아야 반복 수열의 길이가 정확히 나온다

 

m = 2인 경우

 

0,1 , period = 1

 

0,1,1 구하고 a0 = 1, a1 = 1이라 period = 2이고 다음 반복문으로

 

0,1,1,0 구하고 a0 = 1, a1 = 0인데.. period = 3이고

 

사실 여기서 끝나야 하지만, 컴퓨터는 여기서 끝나야 한다는걸 모르기 때문에 한번 더 해줘야한다.

 

0,1,1,0,1 구하고 a0 = 0, a1 = 1이라 이제 반복이 되는구나 알수 있고, period = 3을 print하면 된다.

 

이렇게 하면 period가 정확히 반복 수열의 길이 3으로 된다.

 

만약 period = 2로 하면, 끝나는 시점에 한번 더 계산하기 때문에 period = 4가 된다. 

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    n,m = map(int,stdin.readline().split())

    a0,a1 = 0,1

    period = 1

    for _ in range(m*m):
        
        a0,a1 = a1,(a0+a1)%m

        if a0 == 0 and a1 == 1:
            
            print(n,period)
            break
        
        else:
            
            period += 1

 

4. 피보나치 수열에의 적용

 

2749번: 피보나치 수 3 (acmicpc.net)

2749번: 피보나치 수 3

 

mod = 1000000 이고 이에 대한 피사노 주기를 먼저 구해준다.

 

사실 위에서 제시한 피사노 주기 성질 $k(10^{n}) = 15 * 10^{n-1}$을 알고 있다면 바로 구할 수 있지만, 모르더라도

 

직접 주기를 구하면 되겠다

 

def pisano(m):
    
    a0,a1 = 0,1
    
    period = 1
    
    for i in range(m*m):

        a0,a1 = a1,(a0+a1)%m
        
        if (a0 == 0 and a1 == 1):

            return period

        else:

            period += 1

 

이러고 m = 1000000을 넣어보면 period = 1500000가 나온다.

 

따라서 n번째 피보나치 수열의 항을 m으로 나눈 나머지를 구하라고 한다면 어떻게 접근할 수 있을까?

 

주기 period만큼 반복되므로 우리는 n을 period로 나눈 나머지 n%period번째 항을 구하면 더 빨리 구할 수 있다.

 

즉 n번째 피보나치 수열 항의 m으로 나눈 나머지는 n%period번째 항의 m으로 나눈 나머지와 동일하다.

 

from sys import stdin

mod = 1000000

n = int(stdin.readline())

n = n % 1500000

dp = [0]*(n+1)

dp[1] = 1

for i in range(2,n+1):
    
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])

 

 

 

Fibonacci Number modulo M and Pisano Period - GeeksforGeeks

Fibonacci Number modulo M and Pisano Period - GeeksforGeeks

 

 

피보나치 수를 구하는 여러가지 방법 (acmicpc.net)

피보나치 수를 구하는 여러가지 방법

 

 

Pisano period - Wikipedia

Pisano period - Wikipedia