問題
素数 $p$ と $\mathbb{F}_p$ 上の多項式 $f(x)$（次数 $\le D$）が与えられる。$f(x)$ のスクエアフリー部分を求め、さらに $\mathbb{F}_p$ 上で既約多項式の積に完全因数分解し、次数の小さい順に出力せよ。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $p$ | $2 \le p \le 10^9$ | 素数 |
| $D$ | $1 \le D \le 400$ | 多項式の次数 |
| $c_i$ | $0 \le c_i < p$ | 係数 |
入出力例
入力例1
7
4
1 0 0 0 1出力例1
(x + 2)(x + 5)(x^2 + 3x + 4)$\mathbb{F}_7$ 上で $x^4+1 = (x+2)(x+5)(x^2+3x+4)$。
概念図: 因数分解の3段階
ヒント
ヒント1（方向性）
有限体上の多項式 GCD は多項式のユークリッド互除法で求められる（係数を mod p で計算）。因数分解は3段階：スクエアフリー化 → DDF（同次因子分離）→ Cantor-Zassenhaus（乱択）。
ヒント2（アプローチ）
DDF: $x^{p^i} - x \bmod f$ の GCD を次数 $i=1,2,...$ と順に取ると、次数 $i$ の既約因子の積が分離できる。Cantor-Zassenhaus: 次数 $d$ の既約因子が複数あるとき、乱択多項式 $t$ に対し $t^{(p^d-1)/2}-1 \bmod g$ との GCD で約 $1/2$ の確率で分離。
ヒント3（ほぼ答え）
def ddf(f):
factors = {}
xpow = [0, 1] # x
g = f[:]
i = 1
while 2*i <= len(g)-1:
xpow = poly_powmod(xpow, MOD, g) # x^(p^i)
h = poly_gcd(poly_sub(xpow, [0,1]), g)
if len(h) > 1:
factors[i] = h
g, _ = poly_divmod(g, h)
i += 1
if len(g) > 1:
factors[len(g)-1] = g
return factors模範解答
import sys
from random import randint
def solve():
data = sys.stdin.read().split()
p = int(data[0]); D = int(data[1])
coeffs = list(map(int, data[2:2+D+1]))
MOD = p
def norm(f):
while f and f[-1] == 0: f.pop()
if f and f[-1] != 1:
inv = pow(f[-1], MOD-2, MOD)
f = [(c*inv)%MOD for c in f]
return f if f else [0]
def pmul(a, b):
if not a or not b: return [0]
r = [0]*(len(a)+len(b)-1)
for i,ca in enumerate(a):
for j,cb in enumerate(b):
r[i+j] = (r[i+j]+ca*cb)%MOD
return norm(r)
def pdivmod(a, b):
a = a[:]
b = norm(b[:])
db = len(b)-1
inv = pow(b[-1], MOD-2, MOD)
q = []
while len(a)-1 >= db:
c = a[-1]*inv%MOD
q.append(c)
for i in range(db+1):
a[len(a)-1-i] = (a[len(a)-1-i]-c*b[db-i])%MOD
a.pop()
q.reverse()
return norm(q), norm(a)
def pmod(a, b): return pdivmod(a, b)[1]
def psub(a, b):
n = max(len(a),len(b))
r = [0]*n
for i,c in enumerate(a): r[i]=(r[i]+c)%MOD
for i,c in enumerate(b): r[i]=(r[i]-c)%MOD
return norm(r)
def pgcd(f, g):
f, g = norm(f[:]), norm(g[:])
while g != [0]: f, g = g, pmod(f, g)
return norm(f)
def ppowmod(base, exp, mod_p):
r = [1]
base = pmod(base, mod_p)
while exp:
if exp&1: r = pmod(pmul(r, base), mod_p)
base = pmod(pmul(base, base), mod_p)
exp >>= 1
return r
def pderiv(f):
if len(f)<=1: return [0]
return norm([(i*f[i])%MOD for i in range(1,len(f))])
def squarefree(f):
fd = pderiv(f)
if fd == [0]: return f
g = pgcd(f, fd)
if len(g)==1: return f
return norm(pdivmod(f, g)[0])
def ddf(f):
factors = {}
xpow = [0,1]
g = f[:]
i = 1
while 2*i <= len(g)-1:
xpow = ppowmod(xpow, MOD, g)
h = pgcd(psub(xpow,[0,1]), g)
if len(h)>1:
factors[i] = h
g = pdivmod(g, h)[0]
i+=1
if len(g)>1: factors[len(g)-1] = g
return factors
def cz(f, d):
if len(f)-1 == d: return [norm(f)]
results = []; stack = [norm(f)]
while stack:
h = stack.pop()
if len(h)-1 == d: results.append(h); continue
while True:
t = norm([randint(0,MOD-1) for _ in range(2*d)])
if len(t)<=1: continue
tp = ppowmod(t, (MOD**d-1)//2, h)
tp[0] = (tp[0]-1)%MOD
g = pgcd(tp, h)
if 1 < len(g)-1 < len(h)-1:
stack.append(norm(g))
stack.append(norm(pdivmod(h,g)[0]))
break
return sorted(results, key=lambda f: len(f))
f = norm(coeffs)
sf = squarefree(f)
dd = ddf(sf)
irr = []
for d, g in sorted(dd.items()):
irr.extend(cz(g, d))
def p2s(f):
terms = []
for i in range(len(f)-1,-1,-1):
if f[i]==0: continue
if i==0: terms.append(str(f[i]))
elif i==1: terms.append("x" if f[i]==1 else f"{f[i]}x")
else: terms.append(f"x^{i}" if f[i]==1 else f"{f[i]}x^{i}")
return " + ".join(terms) if terms else "0"
print("".join(f"({p2s(g)})" for g in irr))
solve()Step-by-Step 解説
Step 1: スクエアフリー化
$f = g^2 h$ なら $f' = 2g g' h + g^2 h'$、よって $\gcd(f, f')$ に $g$ が含まれる。$f / \gcd(f, f')$ で重複因子を除去。
Step 2: DDF（同次因子分離）
$\mathbb{F}_p$ 上で $x^{p^i} - x$ が全ての次数 $i$ の既約多項式の積で割り切れる。$i=1,2,...$ と順に GCD を取ることで次数 $i$ の既約因子の積を分離。
Step 3: Cantor-Zassenhaus（同次因子の分割）
同じ次数 $d$ の既約因子が複数ある場合、乱択多項式 $t$ を使い $t^{(p^d-1)/2}-1 \bmod g$ との GCD を計算。約 $1/2$ の確率で非自明な因子が得られる。
| フェーズ | 計算量 | 特徴 |
|---|---|---|
| スクエアフリー化 | $O(D^2)$ | 決定論的 |
| DDF | $O(D^2 \log p \cdot D)$ | 決定論的 |
| Cantor-Zassenhaus | 期待 $O(D^2 \log p)$ | 乱択（期待反復回数 2） |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| スクエアフリー化をスキップ | DDF が誤動作する | 必ず squarefree を先に実行 |
poly_powmod の指数を固定 | DDF で正しい次数が取れない | ループ内で指数を p に固定して逐次乗算 |
C-Z で exp = (p-1)//2 | $d>1$ のとき正しくない | exp = (p^d-1)//2 を使う |
次のステップ
発展問題: 標数 $p^k$ の拡大体上での因数分解（Hensel lifting）