應用：多項式的解數

這邊我們先假設 \(p=998244353\) 是個大家最喜歡的質數吧。

第一種想法：利用 NTT

總之 NTT 會帶給你 \(f(0), f(1), \ldots, f(p-1)\) 的值，算完之後就可以知道有幾個解啦。 這個時間複雜度是 \(O(n+p\log p)\) (吧）

小插曲：利用 NTT 計算多項式乘法

如果要把模 \(p\) 底下的兩個多項式 \(f, g\) 乘起來，且這兩個多項式的度數都不超過 \(n\)。 那麼使用 NTT 我們可以在 \(O(n\log n)\) 時間內計算出乘積 \(fg\)。

第二種想法：兩個多項式的最大公約式

若 \(f(x)\) 在模 \(p\) 底下有解 \(r_1, r_2, \ldots, r_t\)，那麼我們能將 \(f(x)\) 寫成形如： \[f(x)\equiv (x-r_1)^{k_1}(x-r_2)^{k_2}\cdots (x-r_t)^{k_t} g(x)\] 的形式，其中 \(k_1, k_2, \ldots, k_t\ge 1\) 為正整數，\(g(x)\) 也是一個整係數多項式，而且 \(g(x)\) 在模 \(p\) 底下毫無整數解。

如果我們將 \(f(x)\) 與 \(h(x):=x(x-1)(x-2)\cdots (x-(p-1))\) 拿去找出最大公約式 (這個在歐幾里德整環來說能夠被良好地定義出來)，這個最大公約式就必定會是我們想要的： \[\gcd(f(x), h(x)) = (x-r_1)(x-r_2)\cdots (x-r_t)。\]

而使用這個方法的好處有兩個：其一，如果我們只在乎 \(t\) 的值，那麼找出最大公約式以後，它的次數就會是我們要的答案啦！其二，根據費馬小定理，我們會發現 \(h(x)\) 其實根本等於 \(x^p-x\)，非常簡約。 這個簡約的特性，可以讓我們使用反覆平方法或減半平方法加速 \(\gcd(f(x), h(x))\) 的第一步的計算！

注意到 \((x^p-x)\bmod f = (x^p \bmod f) - (x \bmod f)\)，我們可以先關心要怎麼計算 \(x^p\bmod f\)。 而這就簡單啦：若要計算 \(x^k\bmod f\)，可以直接先遞迴求出 \((x^{k/2}\bmod f)\) 之值，然後將之平方然後再取餘數。 (或者是如同 stackoverflow 上面的建議，事先算出 2 的次方除以 \(f\) 的餘數，然後再挑你想要的乘起來。) 注意到 \(n\) 是多項式 \(f(x)\) 的度數。 這邊需要的計算便是兩個最多 \(n\) 次多項式的乘法 (我們可以用 NTT 解決它)、以及一個 \(2n\) 次多項式除以 \(n\) 次多項式的商和餘數。 除法部分的想法基本上來自於 Schönhage，可以參考這份投影片 它給我們的時間複雜度也是 \(O(n\log n)\) 的。

於是乎！套用 Knuth-Schönhage 或是 Stehlé-Zimmermann 的每次度數剖半的分而治之法，就能夠給我們一個 \(O(n\log^2 n)\) 總時間的輾轉相除法啦！

參考資料

• 題源參考、解題討論參考
• Stackoverflow
• MIT 講義
• 芬蘭阿爾托大學 Aalto University 講義

備註

• 爆搜的話使用 Chien Search 搭配預處理 Montgomery Multiplication 可以讓實作快非常非常多。雖然是 \(O(np)\) 時間但是從頭到尾可以只需要加減法和位元運算。
• 我寫得爆炸亂...之後有機會再來好好整理...