피보나치구하기

 

#include <iostream>
using namespace std;

long long fib[1500001];

int main(void) {

	fib[0] = 0, fib[1] = 1;
	int ret;
	long long n;
	cin >> n;
	{
		for (int i = 0; i < 1500000; i++) {
			fib[i + 2] = (fib[i + 1] + fib[i]) % 1000000;
		}
	}

	cout << fib[n % 1500000];


	return 0;
}

피보나치 수를 특정 수로 나누면 반드시 주기를 이룬다

주기 길이가 p일때 n번째 피보나치수를 m으로 나눈 나머지는, n%p번째 피보나치를 m으로 나눈 나머지와 같다

예를 들어 m=10^k일때 k>2면 그 주기는 15*10^(k-1)이다

 

이게 prerequisite한 문제.

이거 없음 못푼다