數(shù)論上

前言

疊甲：本文的許多定義并不是最官方嚴謹?shù)模瞧鋵嵤潜举|相同的，不過更偏實用一點。有部分內容我并沒有寫代碼驗證過，可能有錯，希望發(fā)現(xiàn)問題的大佬能及時指出。歡迎轉載。但如果是全文轉載，請附上原文鏈接。因為博客園與本地的渲染有細微差別，可能會導致有少量格式錯誤，但應該不會影響閱讀，也歡迎大佬指出。

這不是給數(shù)論初學者寫的博客！這是作者在整理各種數(shù)論知識的邊邊角角梳理出來的文章，不保證內容按照難度遞增，而是按照邏輯順序排列的，相關聯(lián)的知識點會放在一起。文章分為前、中、后和配套題目與題解四個部分，分成四偏文章的原因是，放在一起會導致非常卡，猜測是因為文章太大了，每個部分之間有著藕斷絲連的關系，前三部分是知識點，有著互相依賴的邏輯關系（但是保證不會有自己證明自己的情況出現(xiàn)），第四篇是具體的題目，對提分來說更加重要。建議配合食用。

本文很多內容是我之前寫的博客復制過來，修繕了一下，個人感覺比之前寫的更本質，更清晰一點，還有不少內容是我這次整理新學的知識。四篇文章總源碼超過 100 KB，我認為整理的還是比較全面了，沒有涉及到的內容，大概率在數(shù)論練習題里的后記里面提及。

合集鏈接：數(shù)論上，數(shù)論中，數(shù)論下，數(shù)論練習題。

模運算

基本概念

• 模運算 mod

定義：\(a\bmod b = a - \left \lfloor a/b\right \rfloor \times b\) ，一般要求 \(b > 0\)

• 同余

若 \(m | (a-b)\) 則稱 \(a,b\) 同余，記作 \(a \equiv b\pmod m\)（注：下文可能會省略 mod m）

注意到，\(a\equiv b\pmod p\) 等價于 \(a = b + k\times p\)，根據(jù)定義也等價于 \(m | (a-b)\)。

具體要使用哪個式子根據(jù)具體要求而異，要善于使用這三種表達。

• 同余系

如果 \(a \bmod m = b \bmod m\)，則稱 \(a,b\) 屬于 m 的同一同余系。

• 剩余系

一個的集合，每個數(shù)與 m 的模數(shù)都不同，叫做剩余系；如果集合大小為 \(m\) ，可以認為是每個數(shù)與 \([0,m-1]\) 的數(shù)的某個數(shù)一一對應同余，叫做完全剩余系，有些時候完全剩余系會被直接叫做剩余系。

剩余系這個概念在后面證明有概率會用到，還可以幫助分析一些神秘數(shù)論題。

基礎性質

自反性：\(a \equiv a\)

對稱性：若 \(a \equiv b\) 則 \(b \equiv a\)

傳遞性：若 \(a \equiv b\) 且 \(a \equiv c\) 則 \(b \equiv c\);

可加性：若 \(a \equiv b\) 則 \(a+c \equiv b+c\);

可乘性：若 \(a \equiv b\), 且 \(c \equiv d\)，則 \(ac \equiv bd\)

以上性質應該沒必要再講了。

• 可除性

可除性相對較為陌生，但是很有用。

如果要除的數(shù)和模數(shù)互質，那么直接乘逆元即可，不過不互質的時候也有一個小公式：

若 \(ac \equiv bc \pmod m\)，則 \(a \equiv b \pmod{\displaystyle\frac{m}{\gcd(m, c)}}\).

證明：根據(jù)同余定義有 \(m\mid (ac-bc)\) ，則 \(m\mid c(a-b)\)。

不妨兩邊除上一個 \(\gcd(m,c)\) ，用 \(g\) 代表 \(\gcd(m,c)\) ，于是有：\(\frac mg \mid \frac cg(a-b)\)

這樣子有 \(\frac mg\) 和 \(\frac cg\) 互質，這是最關鍵的一步，用因子的角度理解整除，有 \(\frac mg\) 是 \(\frac cg(a-b)\) 的因子，但是又有 \(\frac mg\) 和 \(\frac cg\) 互質，說明 \(a-b\) 一定有一個因子是 \(\frac mg\) ，所以有 \(\frac mg \mid (a-b)\) ，換一種表達方式就是 \(a \equiv b \pmod{\displaystyle\frac{m}{\gcd(m, c)}}\).

證明模數(shù)性質的基本思路是移項后轉整除式。

基礎運算

加減法和乘法不必多說。

除法

逆元

除法就是乘法的逆運算，所以用定義了乘法逆元來替代了除法。

如果有 \(ax\equiv 1 (\bmod p)\)，則稱 \(x\) 是 \(a\) 在模 \(p\) 意義下的乘法逆元，可以把 \(x\) 當成 \(\frac 1a\)。

一般來所，\(p\) 都是質數(shù)，就算 \(p\) 不是質數(shù)時，一般也有 \(a,p\) 互質。當 \(a,p\) 不互質時，\(a\) 在模 \(p\) 意義下沒有逆元。

求逆元的方式：

1. 費馬小定理

可以證明，當 \(p\) 為質數(shù)時，\(a^{p-1}\equiv 1 (\bmod p)\)，于是可以把 \(a^{p-2}\) 當作 \(a\) 的逆元。

證明參考下文歐拉定理的證明。

2. 拓展歐幾里得算法（exgcd）

這相當于解不定方程 \(ax-kp=1\)，解出來了后，再取 \(x\) 在模 \(p\) 意義下的合法解即可。

根據(jù)裴蜀定理， \(a,p\) 不互質時方程無解，也就是說 a 沒有逆元。

3. 卡常小科技

現(xiàn)在要求 \(a\bmod b\) 的逆元，不妨假設我們已經(jīng)求出了 \(b\bmod a\) 的逆元 \(w\)。

則有 \(bw \equiv 1\pmod a\)，那么記 \(\frac{bw-1}{a}=q\)，則有 \(b|aq+1\)，換句話說 \(-q\) 就是我們要求的逆元。

inline ll inv(ll a, ll b) {return 1<a ? b - inv(b%a,a)*b/a : 1;}

本質應該等價與 exgcd。

4. 線性預處理求逆元

假設要求 \(i\) 的逆元，我們設 \(p=k\times i+r\)。于是

這個是 \(O(n)\) 的預處理。

Inv[1] = Inv[0] = 1; for(int i = 2; i <= n; ++i) Inv[ i ] = ( p - p / i ) * Inv[ p % i ] % p;
//或
inline ll inv(ll i) {i == 1 ? 1 : ( p - p / i ) * inv( p % i ) % p;}

5. 同時處理多數(shù)逆元

考慮線性預處理逆元，其實可以使用計算階乘和階乘的逆來替代，這很無腦。

其實計算階乘和階乘的逆的這個方法還可以拓展。

假設要求序列 \(a\) 的所有數(shù)對 \(m\) 取模的結果，那么可以計算一個序列 \(a\) 的前綴積，（如果序列 \(a\) 就是 \(\{1,2,\dots,n\}\) ，那么這一步就等價于計算階乘），然后計算所有數(shù)的積的逆元，然后再倒著推出前綴逆元積。乘一下就得到了每個數(shù)的逆元。復雜度 \(O(n+\log m)\)。如果你熟悉計算階乘和階乘的逆的方法，這并不難理解。

據(jù)說有一個在線 \(O(1)\) 求逆元的科技，但我不會。

除法的一般情況

在極端情況下，\(a,p\) 不互質時，\(a\) 在 \(p\) 意義下沒有逆元，但是仍然可以定義除法運算！比如 \(4 / 2 \pmod 8\) 其實是有意義的。這時候可以嘗試使用可除性。

定義 \(a/x\pmod p\)，為方程 \(a \equiv kx (\bmod p)\) 的合法解 \(k\)。

設 \(g = \gcd(x, p)\)，那么根據(jù)有

先假設 \(a\) 恰好又是 \(g\) 的倍數(shù)（埋下伏筆）。現(xiàn)在 \(x/ g\) 和 \(p/g\) 互質了，所以使用 \(x/g\) 在 \(p/g\) 意義下的逆元，可以得到 \(k\) 在 \(\bmod p/g\) 意義下的唯一解！但是因為 \(k\) 只能確定到 \(\bmod p/g\) 的級別，如果想要把 k 升回到 \(\bmod p\) 意義下時，那么 \(k\) 就會有 \(g\) 個解！比如 \(4\equiv 2k (\bmod 8)\) ，可得 \(k \bmod 4 = 2\)，所以 \(k \bmod 8 = 2 或6\) 。

考慮 \(a\) 不是 \(g\) 的倍數(shù)的情況，

假設此時也有解，而且有解必定有 \(g\) 個解。

但是一個蘿卜一個坑呀，\(p\) 的剩余系里，一共就只有 \(p\) 個數(shù)。如果每個 \(a\) 都被 \(g\) 個 \(k\) 對應了，但是反過來一個 \(k\) 只能對應一個 \(a\)。那這個肯定對應不上呀！那么假設不成立。

那么如果 \(a\) 不是 \(g\) 的倍數(shù)，\(a\) 除 \(x\) 就無解。這樣一來發(fā)現(xiàn)數(shù)量剛好對了。其實反過來想一想這玩意非常的對呀，\(x\) 的倍數(shù)對 \(p\) 取模得到的數(shù)，難道還能不是 \(\gcd(x,p)\) 的倍數(shù)嗎？對于無解，更嚴謹?shù)淖C明可以把它轉不定方程，然后用裴蜀定理解釋。

我一開始以為這是一個很小眾的知識點，但是在整理數(shù)論的過程中，越發(fā)得覺得可除性重要。上面的推導，會在后文中反復出現(xiàn)，一定要深刻理解。后文會把以上推導統(tǒng)稱為可除性。

次冪（歐拉定理）

快速冪自然不必多說，極端情況下需要使用歐拉定理或這拓展歐拉定理限定冪的大小。

費馬小定理&歐拉定理

• 前置：歐拉函數(shù)

定義： \({\varphi(p)}\) 為小于 \(p\) 且與 \(p\) 互質的數(shù)的個數(shù)。

定義式：\(\varphi(p)=\sum_{i=0}^{p-1}[i\bot p]\)。（這里認為 \(0\) 與 \(p\) 不互質）

計算公式：令 \(n = \prod p_i^{c_i}\) ，則 \(\varphi(n)\) = ${n * \prod (1-\frac{1}{p_i})} $ ，其中 \(\prod\) 中每一項表示因數(shù) \(p_i\) 不出現(xiàn)的頻率。

\(\varphi(p)\) 是積性函數(shù)，使用上面公式易得。有關積性函數(shù)的知識詳見數(shù)論下。

當 \(p\) 是質數(shù)時，容易得到 \(\varphi(p)=p-1\)。

• 定理內容

若 \(\gcd(a,p)=1\)，則 \(a^c\equiv a^{c\bmod \varphi(p)}\pmod p\)

\(p\) 是質數(shù)的時候叫做費馬小定理。其中 \(\varphi(p)\) 是 \(p\) 的完全剩余系里面，與 \(p\) 互質的數(shù)的個數(shù)。

• 證明

令比 \(p\) 小且與 \(p\) 互質的集合為 \(\{x_1,x_2,\dots x_{\varphi(p)} \}\)

因為 \(a,p\) 互質，所以集合 \(\{ax_1,ax_2,\dots ax_{\varphi(P)}\}\) 中的數(shù)仍然與 \(p\) 互質，且對 \(p\) 取模后互不相同。

（對前面結論的證明）因為 \(a\) 和 \(x\) 中都無 \(p\) 的因子，所以與 \(p\) 互質。如果有 \(ax_i\equiv ax_j\)，則 \(a(x_i - x_j) \equiv 0\)，\(a\) 沒有 \(p\) 的因子，后面一項比 p 小，所以同余式不成立，所以得出對 \(p\) 取模后互不相同。根據(jù)可除性，并且 \(a,p\) 互質，并且 \(x\) 集合里的數(shù)互不相同，也可以發(fā)現(xiàn)這不成立。

所以兩邊集合在排序后完全等價。

兩邊集合乘起來：

因為 \(\prod x\) 與 \(p\) 互質，所以 \(a^{\varphi(p)} - 1\) 是 \(p\) 的倍數(shù)

\(\therefore a^{\varphi(p)} ≡ 1 (\bmod p)\)

\(\therefore a^c\equiv a^{c\bmod \varphi(p)}\pmod p\)

• 拓展歐拉定理（ \(a\) 和 \(p\) 不用互質）

感性理解：對于 \(a^c \bmod p\) 的值只在 \([0,p)\) 中，而且 \(a^c \equiv a^{c-1}a\)，把乘一個 \(a\) 看做走一步，那么對于任意一個數(shù) (\(a^{c-1}\)) ，那么很容易就能知道它的 后繼 (\(a^c\))。在有限的 \(p\) 的剩余系內，這一定會形成一個循環(huán)。可以證明，這個環(huán)的長度是 \(\varphi(p)\) 的因子。參考 oi-wiki。

這是一個混循環(huán)（環(huán)的前面跟一個尾巴的形式），所以先走 \(\varphi(p)\) 步進入環(huán)，再把剩余的步數(shù)對環(huán)的長度的倍數(shù) \(\varphi(p)\) 取模。寫出來就是 ${a^c\equiv a^{c\bmod \varphi(p)+\varphi(p)}} $

注意：當 \(c \lt \varphi(p)\) 時，這個余數(shù)可能還沒有進入環(huán)，所以只能暴力地去跑快速冪。（也就是公式的第二行）

更深入的理解，更嚴謹?shù)淖C明如下：

首先，\(\gcd(a,p)\neq1\) 時，普通歐拉定理不成立的根本原因是方程 \(ka\equiv 1\pmod p\) 無解。具體原因參考模的可除性。

方程要是想要有解，那么必須得要等式右邊有 \(\gcd(a,p)\) 這個因子。

拓展歐拉定理給出的解決方案是，在等式兩邊同時乘上一些 \(a\) ，這樣右邊就有 \(\gcd(a,p)\) 這個因子了。

這說明 \(a^k\equiv a^c\pmod p\) 這種方程是可能會有解的。（為了方便討論，這里認為 \(k > c\)）

于是套用模的可除性，就變成了 \(a^{k-c}\equiv 1\pmod {\frac pg}\)，其中 \(g = \gcd(a^c,p)\)。

如果 \(\gcd(a^{k-c},\frac pg)\neq 1\) ，那么原方程仍然不可能成立，

否則，當 \(k-c\mid\varphi(\frac pg)\) 時，原方程成立，也就是拓歐給出的公式。

可以感知到，當 \(c\) 比較大的時候，由于 \(g = \gcd(a^c,p)\) 包含了 \(a^{k-c}\) 和 \(p\) 的所有公因子。

所以可以通過增大 \(c\) 使得 \(\gcd(a^{k-c},\frac pg)= 1\)。

卡邁克爾推出了 \(c\) 的下界，叫做卡邁克爾函數(shù)。感興趣可以自己查。

不過我們可以搞一個更松一點的下界，那就是 \(\varphi(p)\)。

使用 \(\varphi\) 的計算公式，容易得到 \(\varphi(\frac pg)\mid \varphi(p)\)。

現(xiàn)在只需要證明 \(\varphi(p)\) 是一個足夠大的 \(c\) 即可。

對于一個 \(a\) 和 \(p\) 都含有的質因子 \(h_i\)，假設 \(a\) 有 \(r_i\) 個，\(p\) 有 \(d_i\) 個。

于是 \(\max_i \frac {d_i} {r_i}\) 就是 \(c\) 的下界。

最極限的情況時 \(r_i = 1\)，那么 \(c= \max d_i\)，只要 \(\varphi(p)\ge \max d_i\) 即可。

這個限制并不嚴，可以多用幾次放縮就能證出來：

\[\varphi(p)\ge h_i^{d_i-1}(h_i-1)\ge h_i^{d_i-1}\ge(1+(h_i-1))^{d_i-1}\ge1+(h_i-1)(d_i-1)\ge d_i \]

注：第四步運用了二項式定理，并只保留了常數(shù)項和第一項。

在回來看拓展歐拉定理的式子：\(a^c\equiv a^{c\bmod \varphi(p)+\varphi(p)}\)，就會覺得無比正確。

爽了。

• 小試牛刀：求冪塔 \(a^{a^{a^{a^{a\dots}}}}\bmod p\).

在指數(shù)上是對 \(\varphi(p)\) 取模，所以如果設上式為 \(f(a,p)\)，則有 \(f(a,p)\equiv a^{f(a,\varphi(p))}+\varphi (p)(\bmod p)\)。遞歸即可。

分析復雜度。這相當于 \(\varphi(\varphi(\varphi(p)))...\) 這樣一直嵌套直到變成 \(1\) 的嵌套層數(shù)。如果 \(p\) 是奇數(shù)，那么根據(jù) \(\varphi(n)={n \times \prod (1-\frac{1}{p_i})}\)， \(\varphi(p)\) 是偶數(shù)。如果 \(p\) 是偶數(shù)，那么上面這個公式里，至少有一項是 \(\frac 12\) ，所以下一次遞歸的 p 至少減半，所以遞歸次數(shù)和復雜度是 \(O(\log p)\) 的。其實可以進一步證明 \(p>2\) 時， \(\varphi(p)\) 是偶數(shù)，不過對分析大致的復雜度意義并不大。

板子題。相逢是問候，這個題的核心就是冪塔的勢能分析，外面套個線段樹即可。白澤教育 本質相同。

原根與階

原根和階，本質上就是一個數(shù)一直乘然后對 \(p\) 取模得到的循環(huán)節(jié)大小。雖然原根并不能稱作是模意義下的冪運算，但是與“冪”有著密不可分的關系，固寫在這里。

首先由歐拉定理可得 \(\forall a\bot p,a^{\varphi (p)} \equiv 1(\bmod p)\)，可以認為 \(\varphi(p)\) 就是一個循環(huán)節(jié)，每多乘 \(\varphi(p)\) 個數(shù)就又能回到起點 \(1\) ，但是這并沒有說明 \(\varphi(p)\) 是一個最小循環(huán)節(jié)，很有可能存在更小的循環(huán)節(jié)。于是可以定義最小的這種循環(huán)節(jié)叫做 \(a\) 在模 \(p\) 意義下的階，記作 \(\delta_pa\)? 。

注意，由可除性可得，如果 \(a,p\) 不互質，那么像 \(a^k \equiv 1\pmod p\) 這種式子根本就不可能成立，所以我們只討論 \(a,p\) 互質時，\(a\) 的原根與階，\(a,p\) 不互質的話，應該需要卡邁克爾函數(shù)，這里不涉及。

階的重要性質：

若 \(a^n \equiv 1 \pmod m\)，則 \(\delta_m(a)|n\)。

顯然成立，但是這個是后面的證明的基礎。

• 計算一個數(shù)的階

1. 階一定是 \(\varphi(p)\) 的約數(shù)。所以暴力枚舉 \(\varphi(p)\) 的約數(shù)，然后暴力用快速冪判斷合法性。復雜度 \(O(C+\sqrt[3]p)\)，\(C\) 指分解質因數(shù)的復雜度。

2. 維護一個臨時變量 \(t\)，初始為 \(\varphi(p)\)。過程中要保證 \(t\) 是 \(\delta_pa\) 的倍數(shù)。只枚舉 \(\varphi(p)\) 的質因子，假設現(xiàn)在枚舉到了 \(p_i\)，如果 \(a^{t/p_i}\equiv 1\pmod p\) ，則把 \(t\) 變成 \(t/p_i\) 。一直重復這個過程，直到 \(a^{t/p_i}\neq 1\pmod p\) 或 \(t\) 已經(jīng)沒有 \(p_i\) 這個因子。然后枚舉 \(p\) 的下一個因子。這個過程有點像"排除法"，如果你理解了上述過程，自然會明白它的正確性。復雜度 \(O(C+\log p)\)，\(C\) 指分解質因數(shù)的復雜度。

如果 \(\delta_pa = \varphi(p)\) ，也就是說，對于 \(a\)， \(\varphi(p)\) 恰好就是它的最小循環(huán)節(jié)，就定義這樣的 \(a\) 是 \(p\) 的原根。

重要性質：如果 \(p\) 剛好是質數(shù)，那么 \(\varphi(p)\) 就是 \(p-1\) ，假設 \(a\) 是 \(p\) 的原根，那么 \(a\) 的 \([1,p-1]\) 次冪都不同，然后 \(p\) 的完全剩余系大小恰好就是 \(p\)，這說明 \(p\) 完全剩余系里，除了 \(0\) 的每一個數(shù)，一定可以和一個 \(a\) 的次冪一一對應！這個性質非常的好呀。

而且可以證明，質數(shù)都有原根。詳見.(沒給證明的原因是我沒看懂)

• 判斷一個數(shù)是否是 \(p\) 的原根

使用計算階的方法計算原根即可。瓶頸在分解質因數(shù)。

• 原根的數(shù)量

對于一個數(shù) \(m\) ，如果存在奇素數(shù) \(p\) 及 \(\alpha \in \mathbf{N}^{*}\) 使得 \(m\in\{p^{\alpha},2p^{\alpha}\}\)，那么它有原根，否則沒有原根。詳見。證明我沒看懂。

這說明很多數(shù)都沒有原根，這正是原根的缺點。

如果 \(m\) 有原根，則**原根的數(shù)量恰好是 \(\varphi(\varphi(m))\) **。

證明：

對于一個質數(shù) \(m\) ，假設 \(g\) 是 \(m\) 的一個原根。現(xiàn)在假設又有一個數(shù) \(q\)，滿足 \(q = g^y\)，且 \(\gcd(y,\varphi (m)) = 1\) ，那么對于 \(m\) 完全剩余系里的任意一個數(shù) \(a\)，都可以被表示為 \(g^x\)，這里的 \(x\) 又可以被表示為 \(ky \bmod \varphi(m)\) ，也就是說 \(a\equiv q^k\) ，這對任意 \(a\) 都成立，于是 \(q\) 也是 \(m\) 的原根。如果 \(\gcd(y,\varphi (m)) \neq 1\)，那么一定存在 \(x\) 不能被表示為 \(ky \bmod \varphi(m)\) （詳見可除性），那么原根的數(shù)量就是滿足 \(\gcd(y,\varphi (m)) = 1\) 的數(shù)量，也就是 \(\varphi(\varphi(m))\).

對于一個非質數(shù) \(m\)，證明會相對繁瑣。

引理：原根的次冪都與 \(m\) 互質。

考慮反證，假設 \(\gcd(g^c,p)\neq1\)，那么對于任意 \(k\ge c\)，\(g^k\equiv g^c\times g^{k-c}\)。

由于 \(\gcd(g^c,p)\neq1\)，使用裴蜀定理容易得到 \(g^k\not\equiv 1\pmod p\) 。

但這顯然是錯的，因為只要 \(k\) 是 \(\varphi(p)\) 的倍數(shù)時，\(g^k\equiv 1\pmod p\)。

這說明了原根的次冪只在與 \(p\) 互質的那些數(shù)里面循環(huán)。并且根據(jù) \(\delta_pg=\varphi(p)\)，原根的次冪會遍歷到每一個與 \(p\) 互質的數(shù)。這說明每一個與 \(p\) 互質的數(shù)都可以表示為原根的次冪，這非常的好呀。

現(xiàn)在把 \(m\) 是非質數(shù)的補丁打上了，剩下的證明與上面一樣。

• 得到原根

我打了個表，對于小于 \(3e8\) 的質數(shù)，\(\varphi(\varphi(m))\over m\) 最小是 \(0.171m\)，這說明原根的密度是很大的。對于非質數(shù)，\(\varphi(\varphi(m))\over m\) 最小只有 \(0.034m\)。

所以我認為直接隨機化找原根即可，然后選擇你喜歡的方法判斷它是否是原根即可。

王元于 1959 年證明了若 \(m\) 有原根，其最小原根是不多于 \(m^{0.25}\) 級別的。

打表甚至可以發(fā)現(xiàn)，有很多素數(shù)的最小原根都是 2 或 3，而且其他的素數(shù)原根大于 10 的概率也不是很大。由此，我們也可以直接從小到大枚舉前面的數(shù)并判斷它是否是原根。

如果需要所有的原根，就先找到一個合法的 \(g\)，然后找到所有滿足 \(\gcd(y,\varphi (m)) = 1\) 的 \(y\) 。于是，所有 \(g^y\) 就是所有原根。

小結：階是次冪的最小循環(huán)節(jié)，原根是階等與 \(\varphi(p)\) 的數(shù)。如果模數(shù)是質數(shù)，每個非零數(shù)都可以表示為原根的次冪。質數(shù)一定有原根。在極端情況下，可能需要判斷一個數(shù)是否是原根和找到 p 的一個原根。

原根的應用：1. 把每個數(shù)都轉成原根的次冪。2. 用來等效替代替代單位根（比如 ntt，\(w_n^1\) 有模意義的條件是 \(n\mid p-1\)）

更多原根內容可見：數(shù)論學習筆記（一）：同余相關（原根） - Orange_new - 博客園。

對數(shù)（BSGS）

\(BSGS\) 是在 \(x, z, p\) 已知的情況下，用來求解 \(x^y \equiv z \pmod p\) 中 \(y\) 的最小值的。我認為這等價于求 \(\log_x z\)，所以放在了這里。

我們考慮將 \(y\) 除以 \(\lceil \sqrt p \rceil\)，可以得到帶余的式子 \(y = a \lceil \sqrt p \rceil + b(b < \lceil \sqrt p \rceil)\)，那么這個式子也可以寫成 \(y = (a + 1)\lceil \sqrt p \rceil) - (\lceil \sqrt p \rceil - b)\)。

現(xiàn)在用 \(c\) 代替 \(a + 1\)，\(d\) 代替 \(\lceil \sqrt p \rceil - b\)，那么 \(y = c\lceil \sqrt p \rceil - d\)，如果 \(x,p\) 互質，那么可以使用 \(x\) 的乘法逆元，把一開始的同余式改寫為 \(x^{c\lceil \sqrt p \rceil} \equiv z \times x^d \pmod p\)。（你能力強的話其實可以一步推到這里）

那么就可以枚舉同余式右邊的 \(d\)，將算出來的值存入一個哈希表，這是在預處理所有可能的 \(z\times x^d\)。再枚舉同余式左邊的 \(c\)，如果查到哈希表中有 \(x^{c\lceil \sqrt p \rceil}\)，那么就找到了答案，總時間復雜度為 \(O(\sqrt p)\).

如果 \(x,p\) 不互質，那么使用模運算的可除性，設 \(g=\gcd(x,p)\) ，如果 \(z\) 不是 \(g\) 的倍數(shù)，根據(jù)之前的推導，\(x\) 的倍數(shù)對 \(p\) 取模得到的數(shù)，難道還能不是 \(\gcd(x,p)\) 的倍數(shù)嗎? 所以無解。如果 \(z\) 是 \(g\) 的倍數(shù)，則有 \(\frac xgx^{y-1}\equiv \frac zg(\bmod \frac pg)\)，然后用 \(BSGS\) 求出 \(y - 1\) 的值即可。

感覺和光速冪的原理很像。有一些復雜度更優(yōu)秀的科技，但是我認為掌握 \(BSGS\) 就完全夠了。

BSGS 的缺點在于，很多時候 \(\sqrt p\) 的時間復雜度是無法接受的。

開根（二次剩余）

求 \(x\)，滿足 \(x^2\equiv n (\bmod p)\)。要求 \(p\) 是奇素數(shù)。如果 \(p\) 不是質數(shù)，需要給 \(p\) 分解質因數(shù)后在想辦法做，感覺比較麻煩，此處不涉及。

參考 ： 這個。

• 解的個數(shù)

除 \(0\) 外，\(x\) 要么有兩個互為相反數(shù)的解，要么沒有。所以有二次剩余的數(shù)的個數(shù)和沒有二次剩余的數(shù)的個數(shù)都是 \(\frac p2\)。(埋伏筆)

證明：\(0\) 比較特殊，先特判掉。如果已經(jīng)得到一個解，那么它的相反數(shù)顯然也是合法解。我們假設存在至少三個解，對于任意兩個不同合法解 \(x_1^2\equiv x^2_2 \equiv n\) ，則有 \((x_1+x_2)(x_1-x_2) = 0\)，因為兩解不同，所以 \(x_1+x_2=0\) ，這說明任意兩解都是相反數(shù)，所以不可能有三個數(shù)互為相反數(shù)。所以要么沒有解，要么有恰好有兩個解。又因為一個數(shù)的平方恰好對應一個數(shù)，但是剛才說明了一個數(shù)開根一定對應了 0 個或兩個數(shù)，而且這些數(shù)都在 \([1,p-1]\) 這個范圍內，所以有無二次剩余的數(shù)都恰好有 \(\frac p2\) 個。

• 歐拉準則

設：

首先根據(jù)費馬小定理，對于非零數(shù)有 \(n^{p-1}\equiv1\)，所以 \(n^{\frac {p-1}2} \equiv \pm1\)。

歐拉準則就是在說 \(n^{\frac {p-1}2} \equiv \left(\frac{n}{p}\right)\)。

這相當于要證明 \(n^{\frac {p-1}2}\equiv 1\) 和 \(n\) 是二次剩余是完全一一對應。

1. n 是二次剩余 \(\Rightarrow n^{\frac{p-1}2} \equiv 1\)

設 \(x^2 \equiv n\) ，于是 \(n^{\frac {p-1}2} \equiv (x^2)^{\frac{p-1}2}\equiv x^{p-1} = 1\).

2. \(n^{\frac {p-1}2} \equiv 1\Rightarrow n\) 是二次剩余。

假設 \(p\) 的原根是 \(g\) ，設 \(n\equiv g^k\)，然后有 \(n^{\frac{p-1}2}\equiv1\)，所以 \(g^{k\frac{p-1}2}\equiv1\).

因為費馬小定理，所以有 \(g^{p-1}\equiv1\).

然后有因為 \(g\) 是原根，根據(jù)原根的定義，可以推到 \(p-1\mid k\frac{p-1}2\)，所以 \(k\) 是偶數(shù)，所以 \(g^{\frac k2}\) 就可以成為 \(n\) 的二次剩余。

\(\Box\)

注意：如果 \(n\) 不是二次剩余，但是有需要 \(\sqrt n\) 時，如果這個題目恰好又只用 \(n\) 這一個數(shù)的二次剩余，可以搞一個類似于虛數(shù)的東西，定義 \(i^2 = n\)，不需要得到 \(i\) 具體時多少。（再次埋下伏筆）

• Cipolla 算法

復雜度：\(O(\log n)\)。

用隨機化找到一個 \(a\)，使得 \(a^2 - n\) 是非二次剩余，這個概率是 \(\frac 12\) ，所以隨機化的復雜度就是對的（伏筆回收）。

定義模意義下的“虛根” \(i^2\equiv a^2-n\)（再次伏筆回收），如果 \(n\) 是二次剩余，那么 \((a + i)^{\frac{p+1}2}\) 及其相反數(shù)是方程的兩個根。

證明：

要證明的有兩件事

1. \((a+i)^{p+1}\equiv n\)

2. \((a+i)^{\frac{p+1}2}\) 的虛部是 \(0\)

一個一個來：

根據(jù)二項式定理，\((a+i)^p\) 只有 \(a^p+i^p\) 兩項沒有 \(p\) 這個系數(shù)，其他的項在模 \(p\) 后就沒了，所以：

（注：最后一步運用了 \(i^2\equiv a^2-n\)）

根據(jù)歐拉準則，因為 \(a^2-n\) 是非二次剩余，所以 \((a^2-n)^{\frac{p-1}2}\) 是 \(-1\) ，于是上式等于：

下一個：

考慮反證法，假設 \((a+i)^{\frac{p+1}2}\equiv A+Bi\) ，并且有 \((A+Bi)^2\equiv n\) ，展開后發(fā)現(xiàn)只有一邊有 \(i\) 的項，這不對，只能說明 B 是 \(0\).

發(fā)明這個算法的人真的是個神仙吶！

補充：如果 \(p\) 不大，而且只求一個特定的數(shù)的二次剩余，直接暴力遍歷 \([1,p-1]\) 驗證即可。

• \(n\) 次剩余

其實也沒有那么嚇人。來一個山寨版但是我認為更好理解的 \(n\) 次剩余。

\(x^n\equiv a\pmod p\)。\(a,p\) 已知，保證 \(p\) 是質數(shù)，求 \(x\)。

按照套路，把 \(a\) 寫成 \(g^b\) （\(g\) 是原根）。

假設 \(x\equiv g^k\) ，現(xiàn)在就有 \(g^{nk}\equiv g^b \pmod p\) 。

這相當于 \(nk\equiv b\pmod {\varphi(p)}\) ，已知 \(n,b\)，要求 \(k\)。

然后再次使用可除性，發(fā)現(xiàn)如果 \(b\) 不是 \(\gcd(\varphi(p),n)\) 的倍數(shù)就無解，否則有 \(\gcd(\varphi(p),n)\) 個解。

只需要使用 BSGS 算一下 \(b\) 就可以得到 \(k\)，就可以得到 \(x\)，就沒了。復雜度是 \(O(\sqrt n)\)。

我目前不會 log 復雜度求 n 次剩余。

我希望 \(n\) 次剩余能讓你理解到原根處理與次冪有關的問題時的便捷性。

kimi 說像求導積分之類的運算在模意義下是可以定義的，但是意義不大。所以我咕掉了。三角函數(shù)。\(\pi, e\) 等我暫時沒有找到很合適的定義。

可以發(fā)現(xiàn)，后面三大運算，都是在圍繞 \(x^n\equiv b\pmod p\) 這個式子做知二求一（默認 P 是常數(shù)），很多數(shù)論題也是在圍繞這個式子做拓展，例如 T661221 買買題（muhammad）。

要注意，這一章節(jié)里，大多數(shù)時候都需要特判 0

建議嘗試數(shù)論練習題里面 “余數(shù)” 這個題。