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

피보나치 수열을 M으로 나누었을 때, 

M으로 나눈 나머지가 일정한 주기를 이룬다는 것을 증명했다고 한다.

 

여기에는 여러가지 있는데,

• m > 2인 경우에 k(m)은 짝수이다.
• 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
• k(m) ≤ m2 - 1
• k(2^n) = 3×2(n-1)
• k(5^n) = 4×5n
• k(2×5^n) = 6n
• n > 2라면, k(10^n) = 15×10(n-1)

이는 아래 링크에서 자세히 볼 수 있다.

https://www.acmicpc.net/problem/9471

 

이를 이용해 N번째 피보나치 수열을 계산할 수가 있는데,

N번째 피보나치 수열의 주기를 구해주고 이를 P라고 하면,

dp[N] == dp[N%P]와 같으므로 

N%P번째 피보나치 수열의 값을 구해주면 된다.

 

아래는 10^6으로 나눈 나머지의 값을 계산하는 코드이므로

주기가 15 * 10^5이 된다.

#include <iostream>
#define num 1000000
#define MAX 1500000
using namespace std;
using ll=long long;
int dp[MAX];
int main() {
    ll n; cin >> n;
    dp[0]=0, dp[1]=1;
    for(int i=2; i<=MAX; i++) dp[i]=(dp[i-1]+dp[i-2])%num;
    cout << dp[n%MAX];
}