피사노 주기 알아보기

피사노 주기(Pisano Period)는 피보나치 수열을 어떤 수 m으로 나뉘었을 때 나타나는 나머지의 순환하는 패턴의 길이를 나타내는데요, 이 주기는 모든 정수 m에 대하여 존재하며 피보나치 수열의 나머지는 결국 반복되는 주기를 가지고 있습니다,

피보나치 수열은 다음과 같은 방식으로 보통 생성이 됩니다

F(0) = 0, F(1) = 1
그리고 n > 1에 대해, F(n) = F(n - 1) + F(n - 2)

이 수열의 각 항을 특정 수 m으로 나눈 나머지를 취하면 나머지들의 순서도 일정한 패턴을 이루며 이 패턴은 결국 "반복"됩니다, 이 반복되는 패턴의 길이를 피사노 주기라고 합니다.

피보나치 수열을 m으로 나눈 나머지가 이처럼 주기를 이루고 있으며
11으로 피보나치 수열을 나누었을 때 10번째 순서를 기준으로 다시 순회하고 있습니다.

그리고 위 그림을 자세히 보면 알 수 있는 사실이지만 10번과 11번이 0과 1으로 나머지값이 생기는데
다른 피사노 주기 역시 마지막 주기가 0이며 다시 처음 시작할 때 무조건 1이 되기 때문에

temp = (currnet + previous) % mod;
previous = current;
current = temp;

이런식으로 피보나치 수열을 m으로 나누어주면서 만약 current 와 previous가 앞서 말한것과 동일하게

if(previous == 0 && current == 1)이 될 경우
여태까지 몇번 순회했는지를 return 해주면 피사노주기를 알 수 있습니다.

아래는 이와 관련된 문제와 코드들입니다 !

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

#include <iostream>
using namespace std;

long long pisano(long long m) {
    long long previous = 0;
    long long cur = 1;
    long long temp;

    for (long long i = 0; i < m * m; i++) {
        temp = (previous + cur) % m;
        previous = cur;
        cur = temp;

        if (previous == 0 && cur == 1) {
            return i + 1;
        }
    }
}

int main() {
	
	int t;
	
	cin >> t;
	
	while(t--) {
		int num, m;
		
		cin >> num >> m;
		
		cout << num << " " << pisano(m) << '\n';
	}
	
	
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int fibo[1500000];

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	long long int n;
	
	cin >> n;
	
	fibo[0] = 0;
    fibo[1] = 1;
 
    for (int i = 2; i < 1500000; i++)
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000;
 
    cout << fibo[n % 1500000] << '\n';

	return 0;
}