이것 저것 &

문제링크:https://www.acmicpc.net/problem/2749

수학적인 개념을 파악하는게 어려웠던 문제... 

접근방식

1. 당연히 일반적인 dp로는 불가능

2. 찾아보니 피사노 주기라는 것이 존재했다. 간단하게 말하면 피보나치수를 n으로 나눈 나머지로 처리할때 m이라는 주기가 생긴다는 것이다. 자세한 설명은 아래 문제를 참고

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

3. 피사노 주기를 구하고 해당 값까지 단순 피보나치를 구현하여 문제를 해결

문제풀이 

1. 피사노 주기 함수를 구현. 단순하게 계속 반복하며 원소값이 0, 1일때를 찾는다. 

2. 피사노 주기만큼 n을 나눈 나머지값 만큼만 탐색해주며 결과를 도출.

정답코드입니다.

#include <iostream>
using namespace std;
//1000000로 나눈 값은 1500000개 만큼의 단위로 반복한다.  feat 피사노 주기 
long long n;

long long get_pisano(long long num) {

	int a = 0, b = 1, result = 0;
	
	for (long long cnt = 1;; cnt++) {
		result = a + b;
		result %= num;
		a = b, b = result;

		if (a == 0 && b == 1) {
			return cnt;
		}	
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	long long temp = get_pisano(1000000);
	n %= temp;

	int a = 0;
	int b = 1;
	int result = 0;

	if (n == 0)
		cout << 0 << endl;
	else if (n == 1)
		cout << a + b << endl;
	else{
		for (int i = 2; i <= n; i++) {
			result = a + b;
			result %= 1000000;
			a = b, b = result;
		}

		cout << result << endl;
	}

	return 0;
}