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

피보나치수열을 m으로 나눈 나머지에서 0과 1이 연속으로 나온다면 주기가 나온 것.

 

#include <iostream>
using namespace std;

int main() {
	int tc, n, m;
	cin >> tc;

	while (tc--) {
		cin >> n >> m;

		int a = 0;
		int b = 1;
		int cnt = 0;

		while (1) {
			if (a == 0 && b == 1 && cnt != 0) {
				break;
			}

			int tmp = a;
			a = b;
			b = (tmp + a) % m;
			cnt++;
		}

		cout << n << " " << cnt << endl;
	}
}