Day 166-Q5 — 2026-09-30 | Pisano 周期（フィボナッチ数列の mod m での周期）

📋 コピーimport sys
from math import gcd
def fibpair(k, m):
    # (F_k, F_{k+1}) mod m を倍加法で
    a, b = 0, 1
    for bit in bin(k)[2:]:
        c = a * ((2*b - a) % m) % m
        d = (a*a + b*b) % m
        if bit == '1': a, b = d, (c + d) % m
        else: a, b = c, d
    return a, b
def factor(x, primes):
    f = {}
    for p in primes:
        if p*p > x: break
        while x % p == 0:
            f[p] = f.get(p, 0) + 1; x //= p
    if x > 1: f[x] = f.get(x, 0) + 1
    return f
def pisano_prime(p, primes):
    if p == 2: return 3
    if p == 5: return 20
    T = p-1 if p % 5 in (1, 4) else 2*(p+1)       # π(p) は T の約数
    for q in factor(T, primes):
        while T % q == 0 and fibpair(T//q, p) == (0, 1 % p):
            T //= q
    return T
def main():
    m = int(sys.stdin.readline())
    LIM = 1500000
    sv = bytearray([1])*(LIM+1); sv[0] = sv[1] = 0
    for i in range(2, int(LIM**0.5)+1):
        if sv[i]: sv[i*i::i] = bytearray(len(sv[i*i::i]))
    primes = [i for i in range(LIM+1) if sv[i]]
    res = 1
    for p, e in factor(m, primes).items():
        pi = pisano_prime(p, primes) * p**(e-1)   # π(p^e)=p^(e-1)π(p)（Wall–Sun–Sun 素数が無い前提）
        res = res // gcd(res, pi) * pi
    print(res)
main()