[C++] 백준 9471번 피사노 주기

백준 2749번 피보나치3을 풀기 전에 이 문제를 풀고가야 한다는 것을 알게 되었다

피사노 주기라는 것은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 의미한다. 

주기를 생각할 때 다시 돌아오는 것은 1, 그 전의 것은 0이 되면 된다. 

그리고 list에 넣을 때 피보나치 수를 직접 넣는 것이 아니라 나머지 연산이 된 값을

집어넣어야 하는 것을 주의하면 될 것 같다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {

	int t;
	int n, m;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n >> m;
		vector<int> fibo_list;
		fibo_list.push_back(0);
		fibo_list.push_back(1);
		fibo_list.push_back(1);

		int temp = 3;
		while (true) {
			fibo_list.push_back((fibo_list.at(temp - 1) + fibo_list.at(temp - 2)) % m);
			if (fibo_list.at(temp - 1) % m == 0 && fibo_list.at(temp - 2) % m == 1)
				break;
			temp++;
		}
		cout << n << " " << temp - 1 << "\n";
	}
	return 0;
}