백준 9471 피사노 주기

www.acmicpc.net/problem/9471

9471번: 피사노 주기

피보나치수열을 m으로 나누면 일정한 주기를 띄게 되는데 그 주기의 길이를 찾는 문제이다.

우선 주기마다 규칙이 있을 거라 판단하고 몇 개의 케이스를 돌려보았다.

 

 

7로 나눈 주기

10으로 나눈 주기

이 외에도 몇개를 더 살펴봤지만 1, 0 숫자가 나온 뒤에 다시 주기가 나오는 것을 확인할 수 있다.

 

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int tc, n, m;
	cin >> tc;

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

		int m1 = 0, m2 = 1, cnt = 0;

		do {
			int tmp = m1;
			m1 = m2;
			m2 = (tmp + m1) % m;
			cnt++;
		} while (m1 != 0 || m2 != 1 || !cnt);

		cout << n << ' ' << cnt << '\n';
	}

	return 0;
}

위와 같은 코드로 m1 이 0이고 m2가 1인 경우로 다시 돌아오면 그 길이가 주기라고 할 수 있다.