2749번: 피보나치 수 3

#include<cstdio>

int main()

{

long long n, a = 0, b = 1, c = a + b;

scanf("%lld", &n);

for (n = n % (1500000); n-- > 1; a = b % 1000000, b = c % 1000000)

c = (a + b) % 1000000;

printf("%lld", c);

}

/*피보나치 수열을 어떤 값으로 나눈 나머지는 주기를 가진다.

나머지를 구하기위해 나눠야하는 수가 10의 k승이고, k가 2보다 크면 주기는 15*(10의 k-1승)이다.

즉, 너무 큰 n을 처음부터 1500000으로 나눠서 계산한다. */