피사노 주기 (Pisano Period)

정의

피사노 주기 (Pisano Period) π(m) 은 피보나치 수열 F_n 을 m 으로 나눈 나머지 수열이 주기적 이 될 때의 최소 주기. 피보나치 수열 mod m 은 항상 주기적이며, 주기는 1, 2, 3, 4, 5, 8, 10, 12, 15, 16, … 등 다양.

대표값: π(2) = 3, π(3) = 8, π(10) = 60, π(10^k) = 15·10^{k-1} (k ≥ 2).

문제 상황과 동기

F_n mod m 을 구하라. n ≤ 10^18, m ≤ 10^6.

• naive (선형 DP): O(n). n=10^18 이면 불가능.
• 행렬 거듭제곱: O(log n) 이지만, m 이 작을 때는 주기가 더 짧음.
• 피사노 주기 활용: 주기 π(m) 을 찾고 F_{n mod π(m)} mod m 만 계산. O(m) 전처리 + O(log n) 또는 O(m) 본연산.

핵심 통찰: 피보나치 mod m 은 유한 상태 자동기 (F_{i}, F_{i+1}) 의 두 쌍 (0, 1) 이 재등장할 때 주기가 시작.

시각화

핵심 아이디어

주기성 증명

m 으로 나눈 나머지 (F_i, F_{i+1}) 는 최대 m² 가지. 비둘기집 원리에 의해 처음 m²+1 항 안에 반드시 같은 쌍이 등장하고, 그 순간부터 주기적.

주기 계산

주기 시작 조건: (F_i, F_{i+1}) == (0, 1)

(0, 1) 이 재등장하면 주기 π(m) 이 발견됨. 피보나치의 성질 상 처음 (0, 1) 이 아닌 (0, 1) 의 재등장이 주기.

주기 성질

• π(m) 은 multiplicative: gcd(a, b) = 1 이면 π(ab) = lcm(π(a), π(b))
• π(p^k) 는 π(p) · p^{k-1} 를 따름 (p ≠ 5 인 소수)
• π(5) = 20 (특수)
• π(2) = 3, π(2^k) = 3·2^{k-1}
• π(10^k) = 15·10^{k-1}

알고리즘

pisano_period(m):
    a = 0, b = 1
    for i in range(m * m):   # m² 번 안에 반드시 발견
        a, b = b, (a + b) % m
        if a == 0 and b == 1:
            return i + 1
    return m * m

fibo_mod(n, m):
    pi = pisano_period(m)
    n = n % pi
    return fibo_dp(n, m)     # O(n) 이지만 n < pi ≤ 6m

구현

// Pisano period + F_n mod m
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
ll pisano(ll m) {
  ll a = 0, b = 1, c;
  for (ll i = 0; i < m * m; i++) {
      c = (a + b) % m;
      a = b; b = c;
      if (a == 0 && b == 1) return i + 1;
  }
  return m * m;
}
​
ll fibo_mod(ll n, ll m) {
  if (n <= 1) return n;
  ll pi = pisano(m);
  n %= pi;
  ll a = 0, b = 1, c;
  for (ll i = 2; i <= n; i++) {
      c = (a + b) % m;
      a = b; b = c;
  }
  return b;
}
​
int main() {
  ll n, m; cin >> n >> m;
  cout << "pi(" << m << ") = " << pisano(m) << "\n";
  cout << "F_" << n << " mod " << m << " = " << fibo_mod(n, m) << "\n";
  return 0;
}

# Pisano period + F_n mod m
def pisano(m):
  a, b = 0, 1
  for i in range(m * m):
      a, b = b, (a + b) % m
      if a == 0 and b == 1:
          return i + 1
  return m * m
​
def fibo_mod(n, m):
  if n <= 1: return n
  pi = pisano(m)
  n %= pi
  a, b = 0, 1
  for _ in range(2, n + 1):
      a, b = b, (a + b) % m
  return b
​
import sys
n, m = map(int, sys.stdin.readline().split())
print(f"pi({m}) = {pisano(m)}")
print(f"F_{n} mod {m} = {fibo_mod(n, m)}")

10 3

pi(3) = 8
F_10 mod 3 = 1

100 10

pi(10) = 60
F_100 mod 10 = 5

복잡도

변형

함정

1. 최대 루프 한도

m * m 반복은 m ≤ 10^6 이면 10^12 로 너무 큼. 실제로는 m 이 커도 주기가 6m 이내. 반복 한도를 6 * m 으로 제한해도 안전.

2. n < pi 인 경우

n % pi 에서 n 자체가 pi 보다 작으면 그냥 n 번째 피보나치를 계산. 이때도 O(pi) 또는 O(log n) 행렬 곱.

3. mod m 의 m 이 1

F_n mod 1 = 0. 주기도 1. 특수 처리.

4. 64-bit 오버플로우

m * m 이 long long 범위 초과 가능. m ≤ 2·10^6 이면 4·10^12 < 9·10^18 이므로 안전. 그 이상이면 __int128 또는 unsigned long long.

BOJ 연습 문제

참고

• 분할 정복을 이용한 거듭제곱 (행렬 거듭제곱)
• 유클리드 호제법 (lcm 계산)
• 소인수분해 (multiplicative 성질)