同余

· · 个人记录

欧拉定理和费马小定理

费马小定理：若 p 为质数，\gcd(a,p)=1，则有 a^{p-1}\equiv 1 \pmod{p}。

欧拉定理：若 \gcd(a,m)=1，则有 a^{\varphi(m)}\equiv 1\pmod {m}。

扩展欧拉定理：a^b\equiv \begin{cases} a^{b \bmod \varphi(m)}, & \gcd(a,m)=1,\\ a^b,& \gcd(a,m)\neq 1,b < \varphi(m),\\a^{(b\bmod \varphi(m))+\varphi(m)},&\gcd(a,m)\neq 1,b \ge \varphi(m).\end{cases}

一般用来在指数上取模或求乘法逆元。

upd：在处理形如 c^{c^{c^{...^{x}}}} 的幂塔形式的式子时，常常使用扩展欧拉定理，注意到幂塔的每层会对 m,\varphi(m),\varphi(\varphi(m)),..,1,1,... 取模，显然对 1 取模的数无所谓，而其他数数量级是 \mathcal O(\log m) 的，也就是说，在幂塔 \mathcal O(\log m) 层之后的值其实对最终的值没有影响，进而解决一些问题，如 P4139 和 P5285。

逆元：p 为质数且 \gcd(a,p)=1 时，有 a^{p-2}\equiv \frac 1a\pmod {p}。

线性同余式

解 ax\equiv b\pmod m。

## 中国剩余定理 解 $$\begin{cases} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\...\\x\equiv a_n\pmod {m_n}\end{cases}$$ 对于所有 $m$ 两两互质的情况，有较轻松的解法。 记 $M=\prod\limits_{i=1}^n m_i,M_i=\frac {M}{m_i}$。令 $c_iM_i\equiv 1\pmod {m_i}$，不难发现 $c_i$ 一定存在。给出结论： $$x\equiv \sum_{i=1}^n M_ic_ia_i\pmod M$$ 证明： 对于 $i\neq j$，必有 $m_i~|~M_j$，所以有： $$x\equiv \sum_{j=1}^n M_jc_ja_j \equiv M_ic_ia_i\equiv a_i\pmod {m_i}$$ 证毕。 当 $m$ 不两两互质时，考虑逐步构造解。 记 $x\equiv p\pmod M$ 为满足了前 $i-1$ 的解，考虑第 $i$ 个同余式 $x\equiv q\pmod m$。 容易得到 $x=p+kM$，带入得到 $p+kM\equiv q\pmod m$，变形一下得到 $kM\equiv q-p\pmod m$，扩展欧几里得解出来 $k$（判掉 $k$ 无解的情况），于是有 $x\equiv kM+p\pmod {{\rm lcm}(M,m)}$。 依次合并这 $n$ 个同余式，最终得到解。 复杂度为 $O(n\log m)$。 ## 素性测试 使用 Miller-Rabin 可以在 $O(\log^2n)$ 的复杂度判断素性。 ### 费马小定理的逆运用 由费马小定理知，$a^{p-1}\equiv 1\pmod p$，因此，随机一个数 $a$ 使得 $n\nmid a$，若 $a^{n-1}\not \equiv 1\pmod n$，则 $n$ 一定为合数。 但以此判定可能会漏掉一些合数。 ### 优化 设 $p-1=u\cdot 2^t$，则 $$a^{u\cdot 2^t}\equiv 1\pmod p$$ $$a^{u\cdot 2^t}-1\equiv 0\pmod p$$ 用平方差展开，得到 $$(a^u-1)(a^u+1)(a^{2u}+1)...(a^{2^{t-1} \cdot u}+1)\equiv 0\pmod p$$ 用这个方法检测正确率更高。 具体地，对于 $n$，令 $n=u\cdot 2^t$，先计算 $a^u$，若 $a^u\equiv 1\pmod n$，直接通过，然后依次平方，如果出现 $a^{u\cdot 2^k}(k<t)$ 使得它模 $n$ 余 $-1$，那么通过检测。如果对于一轮下来都没有通过，那么 $n$ 为合数。 ### 多轮测试 如果只使用一个 $a$ 进行检测，显然正确率不够。 对于 $[2,2^{64})$ 内的数，只需让前 $12$ 个素数作为 $a$ 检测即可保证正确率。 也可以采用 $\{2,325,9735,28178,450775,9780504,1795265022\}$ 七个数检测。 或者随机 $8$ 次左右也行。 ## 分解质因数 对于一个合数 $n$，我们期望能找到一个非平凡因子。 如果暴力是 $\sqrt n$，Pollard-Rho 是一种期望 $O(n^{\frac 14})$ 分解非平凡因子的方法。 ### 生日悖论的推论 对于值域在 $[1,m]$ 中随机的数，期望 $O(\sqrt m)$ 个可以使得其中有两个数相同。 ### 利用最大公约数求因数 考虑一个数 $x$，如果 $1<\gcd(x,n)<n$，那么就找到了 $n$ 的一个因数 $\gcd(x,n)$。 凭空猜想一个函数 $f(x)=(x^2+c)\bmod n$，其实她有很好的性质： 若 $m\mid n,x\equiv y\pmod m$，则 $f(x)\equiv f(y)\pmod m$。 并且 $f(x)$ 最终一定进入循环。 考虑随机 $c$ 和初始值 $x_0$，令 $x_i=f(x_{i-1})$，去除循环部分得到序列 $\{x_0,x_1,...,x_m\}$。由生日悖论知 $X$ 中有 $O(\sqrt n)$ 个不同的值。 令 $p$ 为 $n$ 的最小质因数，令 $y_i=x_i\bmod p$，同理可知 $Y$ 中有 $O(\sqrt p)$ 个不同的值，同时由 $p\le \sqrt n$ 得到 $O(\sqrt p)\le O(n^{\frac 14})$。 假如我们找到两个数 $i,j$，使得 $x_i-x_j\not \equiv 0\pmod n$ 且 $y_i-y_j\equiv 0\pmod p$，那么取 $\gcd(|x_i-x_j|,n)$ 就得到了 $n$ 的一个非平凡因子。而由上面的结论，我们知道这里的复杂度是期望 $O(n^\frac 14)$ 的。 ### Floyd 判环实现 Pollard-Rho 用两个值 $x,y$，初始时随机 $c,x_0$，令 $x\gets x_0,y\gets f(x_0)$，每次计算 $\gcd(|x-y|,n)$，如果 $1<\gcd(|x-y|,n)<n$，那么找到非平凡因子，返回。 否则继续，令 $x\gets f(x),y\gets f(f(y))$。 如果 $x=y$，说明进入循环，继续检测没有意义，分解失败。 多次重复这个过程，直到找到一个非平凡因子。期望复杂度是 $O(n^\frac 14\log n)$，实际比较玄学。 一种实现的优化是用 $k$ 记录一段 $|x-y|$ 的乘积，然后每隔 $l$ 次计算 $\gcd(k,n)$，大概设 $l=O(\log n)$，就平衡掉 $\gcd$ 的复杂度，做到 $O(n^\frac14)$，但这样会增加 $\gcd(k,n)=n$ 的概率，实际效率可能不佳。 还有一种我自己发现的优化是可以先尝试 $100$ 以内的质数，如果能分解直接返回。再搭配上面的优化可以快很多。 求 $\gcd$ 用 `binary-gcd` 的方式实现也能加速。 ## 威尔逊定理 $$(p-1)!\equiv -1\pmod p$$ 利用类似的思想，可以做这样的问题： 求 $\prod\limits_{i=1}^n \frac {i}{\gcd(i,p)}\bmod p$，记为 $(n!)_p\bmod p$，也就是将 $n!$ 去除所有质因子 $p$ 后模 $p$ 的值。 打一个简单的表，容易发现一些规律： $1,2,...,p-1,\frac pp,p+1,p+2,...,2p-1,\frac {2p}{p},...,p^2-p+1,...,p^2-1,\frac {p^2}{p^2},... 1,2,...,p-1,{\color{red}1},1,2,...,p-1,{\color{red}2},1,2,...,{\color {red}1},...

不难发现，(n!)_p\bmod p 由 \lfloor \frac np\rfloor 个 (p-1)!，一个 (\lfloor \frac np\rfloor!)_p，和最后部分，也就是 (n\bmod p)! 组成。得到公式：

(n!)_p\equiv (\lfloor \frac np\rfloor!)_p\cdot ((p-1)!)^{\lfloor \frac np\rfloor}\cdot (n\bmod p)!\pmod p

而 (p-1)!\equiv -1\pmod p 可以做进一步简化。

于是做到 O(p\log n) 的复杂度，如果预处理 p 以内的阶乘能做到 O(p)-O(\log n)。

这个公式可以推广到 (n!)_p\bmod p^k。

具体地，由类似的推导，得出：

(n!)_p\equiv (\lfloor \frac np\rfloor!)_p\cdot ((p^k-1)!)_p^{\lfloor \frac n{p^k}\rfloor}\cdot ((n\bmod p^k)!)_p\pmod {p^k}

对于 i\le p^k，预处理 (i!)_p，做到 O(p^k)-O(\log n) 的复杂度（累加 \lfloor \frac n{p^k}\rfloor，再统一计算 ((p^k-1)!)_p 即可）。

用于分子分母是阶乘，且分母出现 p ，最后要对 p^k 取模的情况（exLucas）。

Lucas / exLucas

求 \dbinom nm\bmod p。

结论：

\binom nm\equiv \binom {\lfloor \frac np\rfloor}{\lfloor \frac mp\rfloor}\cdot \binom{n\bmod p}{m\bmod p}\pmod p

即 n,m 的 p 进制表示下每一位求组合数的积。

求 \dbinom nm\bmod k。

令 k=\prod p_i^{\alpha_i}，只需计算 \dbinom nm\bmod p^{\alpha} 再用中国剩余定理合并出答案即可。

相当于求 \dfrac {n!}{m!(n-m)!}\bmod p^{\alpha}，先算 n!,m!,(n-m)! 中含 p 这个质因子的次数，分别即为 x,y,z，于是答案即为

\frac {(n!)_p}{((n-m)!)_p(m!)_p}\cdot p^{x-y-z}

注意到此时分母不含质因子 p，模 p^{\alpha} 意义下有逆元，于是整个式子直接算算就行。

阶与原根

记 \delta_m(a) 表示满足 a^k\equiv 1\pmod m 的最小正整数 k。

当 g 满足 \delta_m(g)=\varphi(m) 时，称 g 为模 m 的原根。

性质

若模 $m$ 有原根，则共有 $\varphi(\varphi(m))$ 个不同的原根。 若 $g$ 为模 $m$ 的一个原根，则 $g^{k}$ （其中 $\gcd(k,\varphi(m))=1$）均为模 $m$ 的原根。 记 $g$ 为模素数 $p$ 的原根，则 $g,g^2,...,g^{p-1}$ 为 $1$ 到 $p-1$ 的排列，也就是说，任何一个数 $x$ 存在 $X$ 满足 $g^{X}\equiv x\pmod p$。这将允许我们在模意义下取对数，从而将幂变为乘，乘变为加，将运算简单化。 模素数 $p$ 的最小原根 $g_p$ 是 $\mathcal O(p^{0.25})$ 级别的。 $m$ 存在原根当且仅当 $m=2,4,p^n,2p^n$，其中 $p$ 为奇素数。 设 $m\ge 3$，$\gcd(g, m)=1$，则 $g$ 为模 $m$ 的原根当且仅当对于 $\varphi(m)$ 的每个素因子 $p$，有 ${g^{\frac {\varphi(m)}p}} \not\equiv1\pmod m$。 ## 离散对数 求 $a^x\equiv b\pmod m$ 的最小自然数解。 ### BSGS 当 $\gcd(a,m)=1$ 时，有 $a^{\varphi(m)}\equiv1\pmod m$，所以 $x$ 有解，则 $x<\varphi(m)$。 于是采用一种分块算法，令 $B=\lceil \sqrt m\rceil$，设答案为 $x=pB-q(1\le p,q\le B)$，则 $a^{pB-q}\equiv b\pmod m$，由 $\gcd(a,m)=1$ 得到 $a^{pB}\equiv a^{q}b\pmod m$。 于是可以处理 $b,ab,a^2b,...,a^Bb$ 的所有值，存入哈希表，然后枚举 $a^B,a^{2B},a^{3B},...,a^{B^2}$，看对应的值是否存在即可。 ### exBSGS 当 $\gcd(a,m)\ge1$ 时，不一定能得到 $a^{pB}\equiv a^{q}b\pmod m$，考虑把 $a,m$ 化为互质，注意到原方程相当于 $a^x+ym=b$，设 $\gcd(a,m)=d>1$，若 $d\nmid b$，则原方程无解，否则解方程 $\frac ad \cdot a^{x-1}+y \cdot \frac md=\frac bd$，若 $\gcd(a,\frac md)=d_2>0$，继续进行如上过程，令所有 $\gcd>1$ 的分别为 $d_1,d_2,..,d_k$，$\prod\limits_{i=1}^kd_i=D$，则有 $$a^{x-k}\cdot \frac{a^k}{D}+y\cdot \frac mD=\frac bD$$ 此时 $\gcd(a,\frac mD)=1$，于是直接 BSGS 计算 $a^x\equiv \frac bD\pmod {\frac mD}$，再加上 $k$ 即可。 但可能还有 $x\le k$ 的答案，在约 $\gcd$ 过程中验证 $a^i (i\le k)$ 是否为同余式的解即可。 BSGS 和 exBSGS 的复杂度均为 $\mathcal O(\sqrt m)$。 ## 素数模数下的高次剩余 求 $x^a\equiv b\pmod p$。$p$ 为素数。 记 $g$ 为 $p$ 的原根，设 $x\equiv g^c\pmod p$，则 $(g^c)^a\equiv b\pmod p$，所以有 $(g^a)^c\equiv b\pmod p$，BSGS 求出 $c$，再求 $g^c$ 就得到了 $x$。 ## 二次剩余 以下 $p$ 一般指奇素数。 解决如 $x^2\equiv a\pmod p$ 类型的问题。 若存在 $x$ 使得 $x^2\equiv a\pmod p$，且 $p\nmid x$，则称 $a$ 是模 $p$ 的二次剩余（$\rm QR$），否则称 $a$ 是模 $p$ 的二次非剩余 （$\rm NR$）。 记 $P=\frac{p-1}2$。 ### 对称性 即 $a^2\equiv (p-a)^2\pmod p$，也就是说二次剩余总是成对且对称出现。 所以 $1^2,2^2,...,P^2\bmod p$ 包含了模 $p$ 的所有二次剩余，并且它们**互不相等**。 证明： 若 $a_1^2\equiv a_2^2\pmod p (0<a_1,a_2\le P)$， 则 $p\mid a_1^2-a_2^2$，得到 $p\mid (a_1-a_2)(a_1+a_2)$。 因为 $a_1+a_2<p$ 且 $p$ 为素数，所以 $p|a_1-a_2$，又因 $|a_1-a_2|<P<p$，所以 $a_1-a_2=0$。证毕。 这说明模 $p$ 意义下恰好存在 $P$ 个二次剩余和 $P$ 个二次非剩余。 ### 乘法法则 $${\rm QR}\times{\rm QR}={\rm QR}~,~{\rm QR}\times{\rm NR}={\rm NR}~,~{\rm NR}\times{\rm NR}={\rm QR}$$ 证明： 设 $a_1\equiv b_1^2 \pmod p,a_2\equiv b_2^2\pmod p$，则 $a_1a_2\equiv b_1^2b_2^2\equiv(b_1b_2)^2\pmod p$。${\rm QR}\times{\rm QR}={\rm QR}$ 得证。 设 $a_1\equiv b_1^2 \pmod p$，$a_2$ 为 ${\rm NR}$，假设 $a_1a_2$ 为 ${\rm QR}$，且 $a_1a_2\equiv b_3^2 \pmod p$，则 $b_1^2a_2\equiv b_3^2\pmod p$，设 $c_1b_1\equiv 1\pmod p$，则 $b_1^2c_1^2a_2\equiv b_3^2c_1^2\pmod p$，即 $a_2\equiv (b_3c_1)^2\pmod p$，这与 $a_2$ 为 ${\rm NR}$ 矛盾，故 $a_1a_2$ 为 ${\rm NR}$。${\rm QR}\times{\rm NR}={\rm NR}$ 得证。 设 $a$ 为 ${\rm NR}$。我们知道 $a,2a,...,(p-2)a,(p-1)a$ 在模 $p$ 意义下相当于 $1,2,...,p-1$ 的重排，由于 $1,2,...,p-1$ 中有 $P$ 个 ${\rm QR}$ 和 $P$ 个 ${\rm NR}$，而 ${\rm QR}\times{\rm NR}={\rm NR}$，所以 $a$ 与 $P$ 个 ${\rm QR}$ 乘积分别对应 $P$ 个 ${\rm NR}$，那么 $a$ 与 $P$ 个 ${\rm NR}$ 的乘积只能对应 $P$ 个 ${\rm QR}$。${\rm NR}\times{\rm NR}={\rm QR}$ 得证。 ### Legendre 符号 观察到 ${\rm NR}$ 和 ${\rm QR}$ 的乘法法则与 $1,-1$ 的乘法相近，于是定义 Legendre 符号： $$\left(\frac ap\right)=\begin{cases}1& \text{若 } a \text{ 是模 }p \text{ 的二次剩余},\\-1&\text{若 } a \text{ 是模 }p \text{ 的二次非剩余}.\end{cases}$$ 则根据二次剩余乘法法则有： $$\left(\frac ap\right)\left(\frac bp\right)=\left(\frac {ab}p\right)$$ ### 欧拉准则 $$a^{\frac {p-1}2}\equiv\left(\frac ap\right)\pmod p$$ 证明先咕了。 ### 二次互反律 设 $p,q$ 是不同的奇素数，则 $$\left(\frac {-1}p\right)=\begin{cases}1&p\equiv 1\pmod 4,\\-1&p\equiv 3\pmod 4.\end{cases}$$ $$\left(\frac 2p\right)=\begin{cases}1&p\equiv \pm1\pmod 8,\\-1&p\equiv \pm3\pmod 8.\end{cases}$$ $$\left(\frac qp\right)=\begin{cases}\left(\frac pq\right)&p\equiv 1\pmod 4 \text{ 或 } q\equiv 1\pmod 4,\\-\left(\frac pq\right)&p\equiv q\equiv3\pmod 4. \end{cases}$$ 证明先咕了。 ### Cipolla 算法 可以求解 $x^2\equiv n\pmod p$，其中 $p$ 为奇素数。 首先由欧拉准则，若 $n^P\equiv -1\pmod p$，直接无解。 考虑找到一个数 $a$，使得 $a^2-n$ 为 ${\rm NR}$，由于 ${\rm NR}$ 的数量为 $P$，期望 $2$ 次左右就可以随机出来一个 $a$。 令 $i^2\equiv a^2-n\pmod p$，但 $a^2-n$ 为 ${\rm NR}$，按理说不存在一个整数 $i$，于是可以将这个数看作模意义下的虚数。 引理 $1$： $$(a+b)^p\equiv a^p+b^p\pmod p$$ 证明： $$(a+b)^p\equiv \sum_{i=0}^p \binom{p}{i}a^ib^{p-i}\pmod p$$ 由于对于 $1\le i<p$ 有 $p|\binom pi$，故： $$(a+b)^p\equiv a^p+b^p\pmod p$$ 证毕。 引理 $2$： $$i^p\equiv -i\pmod p$$ 证明： $$i^p\equiv i\cdot (i^2)^{\frac {p-1}2}\equiv i\cdot(a^2-n)^{\frac {p-1}2}\equiv -i\pmod p$$ 证毕。 于是可以证明 $(a+i)^{p+1}\equiv n\pmod p$。 具体地， $$(a+i)^{p+1}\equiv (a+i)(a+i)^p\equiv (a+i)(a^p+i^p)\pmod p$$ 由费马小定理知 $a^p\equiv p\pmod p$，结合引理 $2$ 得到： $$(a+i)^{p+1}\equiv (a+i)(a-i)\equiv a^2-i^2\equiv a^2-(a^2-n)\equiv n\pmod p$$ 证毕。 所以，$(a+i)^{\frac {p+1}2}\equiv x\pmod p$ 为解。 容易证明 $(a+i)^{\frac {p+1}2}\bmod p$ 下的结果不会有带 $i$ 的项。（tip：设 $(a+i)^{\frac {p+1}2}\equiv A+Bi\pmod p$）。 [同学的证明](https://www.luogu.com.cn/paste/935dvs79) 所以，我们只需随机一个 $a$，使得 $a^2-n$ 为 ${\rm NR}$，然后记 $i^2\equiv a^2-n$，计算 $x\equiv (a+i)^{\frac {p+1}2}$ 即可。实现时可定义一个复数类。 期望复杂度 $O(\log p)$。