競技プログラミング総合スレ 66

186 ：デフォルトの名無しさん (ﾌﾞｰｲﾓ MMf6-tIu7)：2023/04/10(月) 13:12:10.43 ID:Sbe/ma/bM.net

mod p で何代入しても0になる多項式は例えば x(x-1)...(x-p+1) でp次を達成できて最適
mod p^n だとこれをn乗すると構成できるので（最適かは知らんが）pn次以下と評価できる
だからpnがd以下の範囲を探索すれば良いが計算量は悪いな