2749 피보나치 수 3

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

피보나치 수를 M으로 나눈 나머지는 항상 주기를 갖는다. 이를 피사노 주기 (Pisano Period) 라고 한다. M=10^k (k>2) 일 때, 주기 P는 15*10^(k-1) 이다.

#include <cstdio>
 
int mod=1000000,p=mod/10*15,f[1500000]={0,1};
 
int main()
{
    for(int i=2;i<p;i++) f[i]=(f[i-1]+f[i-2])%mod;
    long long n;
    scanf("%lld",&n);
    printf("%d",f[n%p]);
    return 0;
}