Day 167-Q5 — 2026-10-01 | Carmichael 関数 λ(n) と乗法位数（φ でなく λ から始め、素因数ごとに割って最小にする）

📋 コピーimport sys
from math import gcd
def sieve(L):
    sv = bytearray([1])*(L+1); sv[0]=sv[1]=0
    for i in range(2, int(L**0.5)+1):
        if sv[i]: sv[i*i::i] = bytearray(len(sv[i*i::i]))
    return [i for i in range(L+1) if sv[i]]
PR = sieve(1000000)
def factor(x):
    f = {}
    for p in PR:
        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 carmichael(fn):
    """λ(n) を素因数分解のかたち {素数: 指数} で返す。fn = n の素因数分解"""
    lam = {}
    def lcm_in(d):
        for q, e in d.items():
            if lam.get(q,0) < e: lam[q] = e
    for p, e in fn.items():
        if p == 2:
            if e == 2: lcm_in({2:1})
            elif e >= 3: lcm_in({2:e-2})
            # e == 1 は λ(2)=1 で何も足さない
        else:
            if e > 1: lcm_in({p:e-1})
            lcm_in(factor(p-1))
    return lam
def order(a, n, lam):
    """gcd(a,n)=1 の a の n を法とする位数。λ(n) から素因数ごとに割っていく"""
    t = 1
    for q, e in lam.items(): t *= q**e
    for q in lam:
        while t % q == 0 and pow(a, t//q, n) == 1 % n: t //= q
    return t
def main():
    data = sys.stdin.read().split()
    n, Q = int(data[0]), int(data[1])
    lam = carmichael(factor(n))
    L = 1
    for q, e in lam.items(): L *= q**e
    print(L)
    for i in range(Q):
        a = int(data[2+i])
        print(order(a, n, lam) if gcd(a, n) == 1 else -1)
if __name__ == "__main__": main()