模意义下的数和运算
取模看起来只是一个很普通的运算，但真正写进代码以后，负数、乘法溢出和模意义下的除法都很容易出错。特别是看到分式时，不能直接把普通除法搬进模运算，而是要先判断分母有没有逆元。
这篇文章从模运算与同余开始，接着介绍扩展欧几里得、线性同余方程、乘法逆元和欧拉定理，最后通过七道例题把这些内容连起来。
模运算与同余
取模的定义
对于整数$a$和正整数$m$，一定存在唯一的整数$q,r$，满足：
$$
a=qm+r,\qquad 0\le r<m
$$
其中$q$是商，$r$是$a$除以$m$得到的余数，记作：
$$
r=a\bmod m
$$
数学中的余数始终位于$[0,m-1]$。但C++中的 % 更接近“取余”，结果与被除数同号，因此：
1 | cout << -3 % 5; // -3 |
而数学意义下的$-3\bmod5$应当等于$2$。如果需要把结果规范到$[0,m-1]$，先取模，再处理负数即可：
1 | i64 x = -3, mod = 5; |
例如：
$$
-3\equiv2\pmod5
$$
同余式：符号$\equiv$表示同余。例如$x\equiv y\pmod p$表示$x$与$y$除以$p$所得的余数相同；上式中，$-3$与$2$除以$5$所得的余数都是$2$。
处理以后$x=2$。
模运算的基本性质
设$m>0$，加法、减法和乘法都可以在运算过程中取模：
$$
(a+b)\bmod m=((a\bmod m)+(b\bmod m))\bmod m
$$
$$
(a-b)\bmod m=((a\bmod m)-(b\bmod m))\bmod m
$$
$$
(ab)\bmod m=((a\bmod m)(b\bmod m))\bmod m
$$
以加法为例，设$a=q_1m+r_1,b=q_2m+r_2$，那么：
$$
a+b=(q_1+q_2)m+(r_1+r_2)
$$
前面的整倍数部分不会影响余数，只需要继续计算$(r_1+r_2)\bmod m$。减法和乘法同理。
减法最容易漏掉负数。例如：
$$
(6-3)\bmod5=3
$$
但分别取余以后得到$1-3=-2$，还要再规范一次。
实际写题时，模数经常固定为$10^9+7$。如果$a,b$已经被规范到$[0,mod-1]$，可以把它设为默认模数：
1 | const int MOD = 1e9 + 7; |
调用常用模数时不必反复传入MOD，遇到其他较小模数时再显式传入第三个参数。addM和subM只修正一次，是因为$a,b$已经在合法余数范围内；若输入可能为负数或超过模数，应先取模并处理负数。乘法先转成i64，避免$a\times b$在取模以前溢出。
这份简洁模板适用于模数不超过$10^9+7$的常见题目。如果模数来自输入并且可能接近i64上限，就不能继续使用int，应改回i64并用i128承接中间结果。后文遇到动态模数时会保留显式的mod参数。
除法不能照搬上面的运算律。例如：
$$
(12\div3)\bmod6=4
$$
但$12\bmod6=0$，先取模再除以$3$只会得到$0$。模意义下的除法需要乘法逆元，后面会专门说明。
同余
如果$a,b$除以$m$得到的余数相同，就称$a,b$模$m$同余，记作：
$$
a\equiv b\pmod m
$$
同余还可以写成更方便证明的形式：
$$
a\equiv b\pmod m\iff m\mid(a-b)
$$
它满足下面这些基本性质：
- 自反性：$a\equiv a\pmod m$；
- 对称性：若$a\equiv b\pmod m$，则$b\equiv a\pmod m$；
- 传递性：若$a\equiv b\pmod m$且$b\equiv c\pmod m$，则$a\equiv c\pmod m$；
- 若$a\equiv b\pmod m,c\equiv d\pmod m$，则$a+c\equiv b+d\pmod m$；
- 若$a\equiv b\pmod m,c\equiv d\pmod m$，则$ac\equiv bd\pmod m$；
- 若$a\equiv b\pmod m$，则$a^k\equiv b^k\pmod m$，其中$k$为非负整数。
同余式不能随意约分。若：
$$
ac\equiv bc\pmod m
$$
只有当$\gcd(c,m)=1$时，才能直接约去$c$并保持模数不变。一般情况下，设$d=\gcd(c,m)$，只能得到：
$$
a\equiv b\pmod{m/d}
$$
这也是模意义下的除法需要先判断互质条件的原因。
扩展欧几里得算法
裴蜀定理
对于不同时为$0$的整数$a,b$，一定存在整数$x,y$，使得：
$$
ax+by=\gcd(a,b)
$$
这就是裴蜀定理。更进一步，线性方程：
$$
ax+by=c
$$
存在整数解，当且仅当：
$$
\gcd(a,b)\mid c
$$
普通欧几里得算法只能求出最大公因数，扩展欧几里得算法还会顺便求出一组满足裴蜀等式的$x,y$。
从 gcd 推到 exgcd
欧几里得算法的递推式为：
$$
\gcd(a,b)=\gcd(b,a\bmod b)
$$
假设递归到下一层以后，已经求出：
$$
bx_1+(a\bmod b)y_1=g
$$
又因为：
$$
a\bmod b=a-\left\lfloor\frac ab\right\rfloor b
$$
代回原式可得：
$$
ay_1+b\left(x_1-\left\lfloor\frac ab\right\rfloor y_1\right)=g
$$
因此当前这一层的系数为：
$$
x=y_1,\qquad y=x_1-\left\lfloor\frac ab\right\rfloor y_1
$$
对应代码如下：
1 | i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) { |
递归边界是$b=0$，此时：
$$
a\times1+0\times0=a
$$
回溯时再按照上面的式子逐层还原系数。整个过程与欧几里得算法的递归层数相同，对于非负且不同时为$0$的$a,b$，时间复杂度为$O(\log\max(a,b))$。
线性方程的全部解
设$g=\gcd(a,b)$，并且 exgcd 求出：
$$
ax_0+by_0=g
$$
如果$g\nmid c$，方程没有整数解；否则将两边同时乘$c/g$，得到一组特解：
$$
x_1=x_0\frac cg,\qquad y_1=y_0\frac cg
$$
全部整数解为：
$$
x=x_1+k\frac bg,\qquad k\in\mathbb Z
$$
$$
y=y_1-k\frac ag,\qquad k\in\mathbb Z
$$
如果题目只要求任意一组解，输出$x_1,y_1$即可；如果要求最小正整数解或限制解的范围，就需要继续调整$k$。
线性同余方程
形如：
$$
ax\equiv b\pmod m
$$
的式子称为线性同余方程。根据同余的定义，它等价于存在整数$y$，满足：
$$
ax+my=b
$$
设$d=\gcd(a,m)$。由裴蜀定理可知，方程有解当且仅当：
$$
d\mid b
$$
如果$d\nmid b$，直接判定无解；否则同时除以$d$：
$$
\frac adx\equiv\frac bd\pmod{m/d}
$$
此时$\gcd(a/d,m/d)=1$，所以$a/d$在模$m/d$意义下存在逆元。设$x_0$是一个解，那么原方程在模$m$意义下共有$d$个不同的解：
$$
x=x_0+k\frac md,\qquad k=0,1,\ldots,d-1
$$
如果只要求最小非负解，只需要把$x_0$规范到$[0,m/d-1]$。这一步很容易写错：解的周期是$m/d$，不是原来的$m$。
乘法逆元与欧拉定理
乘法逆元
若存在整数$x$满足：
$$
ax\equiv1\pmod m
$$
就称$x$是$a$在模$m$意义下的乘法逆元，记作$a^{-1}$。
逆元存在的充要条件是：
$$
\gcd(a,m)=1
$$
如果逆元存在，那么根据同余的定义，存在整数$y$使得：
$$
ax+my=1
$$
这正是裴蜀等式，所以可以使用 exgcd 求出$x$。反过来，如果$d=\gcd(a,m)>1$，那么$d$同时整除$ax$和$my$，不可能整除右边的$1$，逆元也就不存在。
求出$x$以后，还要把它规范到$[0,m-1]$：
1 | i64 x, y; |
有了逆元，模意义下的除法就可以改写为乘法：
$$
\frac ab\equiv a\cdot b^{-1}\pmod m
$$
但前提仍然是$\gcd(b,m)=1$。如果分母没有逆元，就不能使用这个式子。
欧拉函数与欧拉定理
欧拉函数$\varphi(m)$表示$1$到$m$中与$m$互质的整数个数。若$m$的不同质因子为$p_1,p_2,\ldots,p_k$，那么：
$$
\varphi(m)=m\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)
$$
直接分解质因数即可在$O(\sqrt m)$时间内求出$\varphi(m)$。
当$\gcd(a,m)=1$时，欧拉定理给出：
$$
a^{\varphi(m)}\equiv1\pmod m
$$
因此可以对指数按$\varphi(m)$取模：
$$
a^b\equiv a^{b\bmod\varphi(m)}\pmod m
$$
互质条件不能省略。若$\gcd(a,m)>1$，直接把指数对$\varphi(m)$取模可能改变答案。
费马小定理
当$p$是质数时，$\varphi(p)=p-1$。若$p\nmid a$，欧拉定理可以写成：
$$
a^{p-1}\equiv1\pmod p
$$
这就是费马小定理。将两边拆出一个$a$：
$$
a\cdot a^{p-2}\equiv1\pmod p
$$
所以$a$在模$p$意义下的逆元为：
$$
a^{-1}\equiv a^{p-2}\pmod p
$$
指数$p-2$通常很大，需要用快速幂在$O(\log p)$时间内计算。
扩展欧几里得和费马小定理都可以求单个逆元，但适用条件不同：
| 方法 | 模数要求 | 时间复杂度 | 适合场景 |
|---|---|---|---|
| 扩展欧几里得 | $\gcd(a,m)=1$ | $O(\log m)$ | 一般模数下的单个逆元 |
| 费马小定理 | $p$必须是质数且$p\nmid a$ | $O(\log p)$ | 质数模数下的单个逆元 |
如果要求模质数$p$下$1$到$n$的全部逆元，并且$n<p$，还可以线性递推：
$$
inv_i=\left(p-\left\lfloor\frac pi\right\rfloor\right)inv_{p\bmod i}\bmod p
$$
1 | inv[1] = 1; |
这个写法可以在$O(n)$时间内求出全部逆元，不过它依赖$p$为质数且$n<p$，不能不看条件直接套用。
扩展欧拉定理
普通欧拉定理要求$a,m$互质。若题目没有这个保证，但指数$b$很大，可以使用扩展欧拉定理。
当$b<\varphi(m)$时，指数本身不需要处理；当$b\ge\varphi(m)$时：
$$
a^b\equiv a^{b\bmod\varphi(m)+\varphi(m)}\pmod m
$$
这里多加的$\varphi(m)$不能随手删掉。它保证底数与模数不互质时，约去的指数仍然足够大。
如果$b$大到必须用字符串保存，就在读入每一位时计算$b\bmod\varphi(m)$，同时记录$b$是否已经达到$\varphi(m)$。这样不需要真正存下$b$的数值。
常见模型与例题
下面七道题从快速幂开始，依次覆盖扩展欧几里得、线性同余方程、乘法逆元、费马小定理、扩展欧拉定理和任意模数下的等比数列求和。
| 题目 | 核心知识点 | 需要注意的地方 |
|---|---|---|
| 洛谷 P1226 | 快速幂 | 乘法溢出与输出格式 |
| Codeforces 7C | 扩展欧几里得 | 负数系数与无解判断 |
| 洛谷 P1516 | 线性同余方程 | 有解条件与最小非负解 |
| 洛谷 P1082 | 乘法逆元 | 将负数解规范为最小正解 |
| AtCoder ABC156 D | 费马小定理、组合数 | $n$很大，不能预处理到$n$ |
| 洛谷 P5091 | 扩展欧拉定理 | 指数很长且模数不一定为质数 |
| AtCoder ABC293 E | 等比数列取模 | 模数不保证为质数，不能直接相除 |
例题一：洛谷 P1226 快速幂
题目链接：洛谷 P1226【模板】快速幂
给定$a,b,p$，求$a^b\bmod p$。
朴素做法连续乘$b$次，时间复杂度为$O(b)$。当$b$很大时，可以把它拆成二进制。例如：
$$
11=(1011)_2=8+2+1
$$
于是：
$$
a^{11}=a^8\cdot a^2\cdot a
$$
从低位到高位枚举$b$的二进制位。当前位为$1$时，把当前的$a$乘入答案；每处理完一位，就让$a$平方并把$b$右移一位。
1 | i64 mulM(i64 a, i64 b, i64 mod) { return (i128)a * b % mod; } |
循环次数等于$b$的二进制位数，因此时间复杂度为$O(\log b)$，空间复杂度为$O(1)$。
点击展开完整代码
1 | /* Fufffh */ |
例题二：Codeforces 7C
题目链接：Codeforces 7C Line
题目给出$A,B,C$，要求寻找一组整数$x,y$，满足：
$$
Ax+By+C=0
$$
移项以后得到：
$$
Ax+By=-C
$$
设$g=\gcd(A,B)$，方程有整数解当且仅当$g\mid(-C)$。为了让 exgcd 的递归过程更稳定，可以先对$|A|,|B|$求系数，再按照原来的符号修正$x,y$。
若 exgcd 求出：
$$
|A|x_0+|B|y_0=g
$$
将$x_0,y_0$同时乘$(-C)/g$，就得到原方程的一组解。
点击展开完整代码
1 | /* Fufffh */ |
这道题中$A,B,C$都可能为负数，$A$或$B$还可能等于$0$。只要保证传入 exgcd 的两个数非负，并在最后恢复符号，就不需要为这些情况分别写一套算法。时间复杂度为$O(\log\max(|A|,|B|))$，空间复杂度为$O(\log\max(|A|,|B|))$。
例题三：洛谷 P1516 青蛙的约会
题目链接：洛谷 P1516 青蛙的约会
两只青蛙在长度为$L$的环上移动。它们的起点分别为$x,y$，每次分别移动$m,n$，求最少经过多少次移动才能相遇。
经过$t$次移动以后，两只青蛙的位置分别为：
$$
x+tm,\qquad y+tn
$$
要在环上相遇，两者模$L$同余：
$$
x+tm\equiv y+tn\pmod L
$$
移项得到：
$$
(m-n)t\equiv y-x\pmod L
$$
设$a=m-n,b=y-x,d=\gcd(a,L)$。当$d\nmid b$时无解；否则使用 exgcd 求出$a/d$在模$L/d$意义下的逆元，就能得到$t$的最小非负解。
点击展开完整代码
1 | /* Fufffh */ |
这里最关键的是模数要缩小为$L/d$。时间复杂度和空间复杂度均为$O(\log L)$。
例题四：洛谷 P1082 同余方程
题目链接：洛谷 P1082 同余方程
题目要求同余方程：
$$
ax\equiv1\pmod b
$$
的最小正整数解。根据同余的定义，它等价于存在整数$y$，满足：
$$
ax+by=1
$$
输入保证方程有解，因此$\gcd(a,b)=1$。使用 exgcd 求出一组$x,y$以后，$x$可能为负数，但所有解在模$b$意义下属于同一个剩余类。将它规范为：
$$
x\leftarrow(x\bmod b+b)\bmod b
$$
就能得到$[0,b-1]$中的唯一代表。由于$b\ge2$且逆元存在，这个结果不会等于$0$，因此它正是题目要求的最小正整数解。
点击展开完整代码
1 | /* Fufffh */ |
求单个逆元只需要一次扩展欧几里得，时间复杂度和空间复杂度均为$O(\log b)$。
例题五：AtCoder ABC156 D
有$n$种不同的花，每种只有一朵。需要选择至少一朵组成花束，但不能恰好选择$a$朵或$b$朵，求方案数对$10^9+7$取模的结果。
所有非空子集共有：
$$
2^n-1
$$
再减去大小恰好为$a,b$的集合：
$$
ans=2^n-1-\binom na-\binom nb
$$
这里$n$最大达到$10^9$，不能预处理到$n$的阶乘。但$a,b\le2\times10^5$，可以直接使用：
$$
\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}
$$
模数$10^9+7$是质数，并且$k!$不被模数整除，所以：
$$
(k!)^{-1}\equiv(k!)^{mod-2}\pmod{mod}
$$
分子和分母分别计算，再用费马小定理求分母的逆元即可。
点击展开完整代码
1 | /* Fufffh */ |
快速幂和两次组合数计算的总时间复杂度为$O(a+b+\log n+\log MOD)$，空间复杂度为$O(1)$。
例题六：洛谷 P5091 扩展欧拉定理
题目链接：洛谷 P5091【模板】扩展欧拉定理
给定$a,m,b$，求$a^b\bmod m$。其中$m$不保证为质数，$a,m$也不保证互质，并且$b$可能有两千万位，无法使用整数类型保存。
先分解$m$的质因数，求出$\varphi(m)$。随后逐位读取$b$，同时维护：
- $b\bmod\varphi(m)$；
- $b$是否已经达到$\varphi(m)$。
若$b<\varphi(m)$，快速幂的指数仍然是$b$；否则将指数改为：
$$
b\bmod\varphi(m)+\varphi(m)
$$
这样既保留了扩展欧拉定理需要的大小信息，也把真正参与快速幂的指数压到了$2\varphi(m)$以内。
点击展开完整代码
1 | /* Fufffh */ |
设$b$的十进制位数为$L$。求欧拉函数需要$O(\sqrt m)$，处理指数需要$O(L)$，最后一次快速幂需要$O(\log\varphi(m))$；空间复杂度为$O(L)$。
例题七：AtCoder ABC293 E
题目链接：AtCoder ABC293 E Geometric Progression
给定$A,X,M$，求：
$$
S_X=\sum_{i=0}^{X-1}A^i\bmod M
$$
普通等比数列公式为：
$$
S_X=\frac{A^X-1}{A-1}
$$
但题目没有保证$M$是质数，也没有保证$\gcd(A-1,M)=1$，所以$A-1$不一定存在逆元，不能直接使用这个分式。
可以在分治过程中同时维护：
$$
P_n=A^n\bmod M,\qquad S_n=\sum_{i=0}^{n-1}A^i\bmod M
$$
设已经得到$P_k,S_k$，那么：
$$
P_{2k}=P_k^2\pmod M
$$
$$
S_{2k}=S_k+A^kS_k=S_k(1+P_k)\pmod M
$$
如果$n=2k+1$，再补上最后一项$A^{2k}$：
$$
P_{2k+1}=P_{2k}A\pmod M
$$
$$
S_{2k+1}=S_{2k}+P_{2k}\pmod M
$$
每次递归都把$n$减半，不需要任何除法，也不要求$M$为质数。
点击展开完整代码
1 | /* Fufffh */ |
递归深度为$O(\log X)$，每层只进行常数次模乘，时间复杂度和空间复杂度均为$O(\log X)$。
如果还想继续练习，线性同余方程可以做AtCoder ABC186 E Throne，欧拉定理可以做AtCoder ABC222 G 222。Codeforces 710D Two Arithmetic Progressions和Codeforces 906D Power Tower会进一步涉及联立同余方程与欧拉函数链，适合放到后面再做。
总结与常见问题
常见问题
- 为什么 C++ 中负数取模以后还可能是负数？ C++ 的 % 保留被除数的符号；如果需要数学意义下的最小非负剩余，应先令 x%=mod，再在$x<0$时加上$mod$。
- 为什么乘法以后再取模仍然可能出错？ 如果 a*b 先发生整数溢出，后面的取模已经无法挽回。模数较大时应先转成 i128，或使用专门的快速乘。
- 同余式两边能不能直接约分？ 只有被约掉的数与模数互质时，才能保持原模数不变；否则需要缩小模数。
- 线性同余方程什么时候有解？ $ax\equiv b\pmod m$有解，当且仅当$\gcd(a,m)\mid b$。约去最大公因数以后，解的周期是$m/\gcd(a,m)$。
- 逆元什么时候存在？ $a$在模$m$意义下存在逆元，当且仅当$\gcd(a,m)=1$。
- 扩展欧几里得和费马小定理应该用哪一个？ 一般模数使用扩展欧几里得；模数确定为质数时，可以用快速幂计算$a^{p-2}$。
- 费马小定理能不能用于合数模数？ 不能直接使用$a^{m-2}$求逆元。模数不是质数时应先判断互质，再使用扩展欧几里得。
- 指数能不能直接对$\varphi(m)$取模？ 只有$a,m$互质时才能直接使用欧拉定理；不保证互质时，需要保留指数是否达到$\varphi(m)$的信息，再使用扩展欧拉定理。
- 为什么求出的逆元可能是负数？ 扩展欧几里得给出的是一组整数解，负数同样合法。对$x$取模，并在$x<0$时加上模数，就能得到最小非负代表。
- 等比数列为什么不能直接套分式？ 分母$A-1$在当前模数下可能没有逆元。不能确认互质时，应改用分治或矩阵快速幂。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 单次加、减、乘与取模 | $O(1)$ | $O(1)$ |
| 快速幂 | $O(\log b)$ | $O(1)$ |
| 欧几里得算法 | $O(\log\max(a,b))$ | $O(1)$ |
| 扩展欧几里得 | $O(\log\max(a,b))$ | $O(\log\max(a,b))$ |
| 求解线性同余方程 | $O(\log\max(\lvert a\rvert,m))$ | $O(\log\max(\lvert a\rvert,m))$ |
| 扩展欧几里得求单个逆元 | $O(\log m)$ | $O(\log m)$ |
| 费马小定理求单个逆元 | $O(\log p)$ | $O(1)$ |
| 线性求$1$到$n$的逆元 | $O(n)$ | $O(n)$ |
| 质因数分解求$\varphi(m)$ | $O(\sqrt m)$ | $O(1)$ |
| 扩展欧拉处理$L$位指数 | $O(\sqrt m+L+\log\varphi(m))$ | $O(L)$ |
| 分治计算等比数列和 | $O(\log X)$ | $O(\log X)$ |
