백준 문제 2749번 피보나치 수 3 문제풀이 c++

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

2749번: 피보나치 수 3

문제해석

11444번 피보나치 수 6 문제와 똑같은 문제인데 대신 나누는 수가 다르다는 차이점이 있다.

사실 11444번 문제에서 나누는 수만 바꿔서 그대로 제출해도 맞을건데 나누는 수가 10의제곱 꼴이다.

찾아보니 피사노 주기라는 것이 있었다.

피보나치수열을 나누는 수가 10^n이라면 그 나머지가 1.5*10^n만큼의 주기를 갖고 반복된다.

그래서 이 문제에선 100만이므로 150만의 주기를 갖게 되니까 150만 만큼의 공간만 있으면

n이 얼마나 크든 답을 찾을수 있다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
long long int a[1500000];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    a[0]=0;
    a[1]=1;
    long long int n;
    cin>>n;
    int n2=n%1500000;
    for(int i=2; i<=n2; i++)
    {
        a[i]=(a[i-2]+a[i-1])%1000000;
    }
    cout<<a[n2];
}