想定解よりもさらに高速なアルゴリズムが存在するので紹介します。

この問題で見つけたいものは \((f_S x^k + f_T) \bmod g = 0\) と \(\mathrm{deg}(q_0 (f_S x^k + f_T) \bmod f_A) - \mathrm{deg}(g) \leq k - 1\) を満たす最小の \(k\) です。

ここで後者の条件は \(k \geq N \) ならば常に成り立つのでこの範囲では前者の条件のみが重要です。 前者の条件は \(f_T \equiv f_S x^k \pmod g\) と変形できることに注意するとこれは離散対数問題の形になっています。

よって \(k \geq N \) では Baby-Step Giant-Step アルゴリズムを適用し、\(k < N \) では愚直に計算することで全体で \(O(N(N+\sqrt{MN/w})/w)\) などで解くことかできます。 実装例では多項式乗算に PCLMULQDQ を用い乗算を \(O(N^2/w^2)\) で行うことでこの計算量を達成していることに注意してください。

https://atcoder.jp/contests/utpc2023/submissions/50849425