[C++] 백준 2749번 피보나치 수 3

피보나치 수 문제입니다.

피보나치 수는 
arr[n] = arr[n-1] + arr[n-2]의 규칙을 가집니다.
n의 수가 너무 크므로 배열을 만들 수 없습니다.
a = 0;
b = 1;
다음 3줄을 반복하여서 값을 구했습니다.
result = a + b;
a = b;
b = result;

피보나치수열을 나눈 나머지는 일정한 주기를 가집니다.
이 때 나누는 값이 M^n이면 주기는 10 * 10^(k-1)입니다.
나누는 값이 100만이므로 주기는 150만이므로 150만을 나누어주었습니다.

 

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;

int main(int argc, char* argv[])
{
	ll n;
	ll x;
	ll y;
	ll result = 0;

	cin >> n;
	n %= 1500000;

	x = 0;
	y = 1;

	if (n == 1) {
		result = 1;
	}

	for (int i = 2; i <= n; ++i) {
		result = (x + y) % 1000000;
		x = y;
		y = result;
	}

	cout << result << endl;

	return 0;
}