定义#

对于两个数 $a$ 和 $b$ ， $a,b\in \mathbb{Z}$ ，则如果存在整数 $c$ ， $d$ ，使得 $bc+d=a$ ，且保证 $0\leq \lvert{d}\rvert \lt b$ ，则称 $c$ 是 $a$ 除以 $b$ 的商， $d$ 是 $a$ 除以 $b$ 的余数，也被称为 $a$ 模 $b$ 的结果，记作 $a\bmod{b}=d$ ．取模运算和乘除拥有同一运算优先级．

对于两个整数 $a$ 和 $b$ ，如果有整数 $p$ ，使得 $a\bmod{p} = b\bmod{p}$ ，则称 $a$ 和 $b$ 对模 $p$ 同余，记作 $a\equiv b\pmod p$ ，像这样的式子叫做同余方程．

对于两个整数 $a$ 和 $p$ ，如果 $a\equiv 0\pmod p$ ，则 $p$ 整除 $a$ ，记作 $p \mid a$ ．

性质#

同余的基本性质#

对于两个整数 $a,b$ ，如果有 $a\equiv b\pmod p$ ，则可得 $p \mid a - b$

证明：

由已知可得：

\left\{ \begin{aligned} & k_1p+n=a \\ & k_2p+n=b\end{aligned} \right.

其中，

n,k_1,k_2\in\mathbb{Z}

所以：

\begin{aligned} a-b &=k_1p+n-k_2p-n\\ &=k_1p-k_2p\\ &=p(k_1-k_2)\\ &\Rightarrow a-b\equiv 0\pmod p \\ &\Rightarrow p \mid a-b \end{aligned}

加法性质#

对于整数 $a,b,c,d,p$ ，如果有：

\left\{ \begin{aligned} & a\equiv b\pmod p \\ & c\equiv d\pmod p\end{aligned} \right.

则有：

(a+c) \equiv (b+d)\pmod p

证明：

由已知条件可得：

\left\{ \begin{aligned} & k_1p+n=a \\ & k_2p+n=b \\ & k_3p+m=c \\ & k_4p+m=d\end{aligned} \right.

其中，

n,m,k_1,k_2,k_3,k_4\in\mathbb{Z}

所以：

\begin{align*} (a+c)&=k_1p+n+k_3p+m\\&=(k_1+k_3)p+m+n\\(a+c)\bmod p &= m+n\end{align*}

同理：

(b+d)\bmod p=m+n

所以： $(a+c) \equiv (b+d)\pmod p$

加法性质的引申性质#

对于整数 $a,b,c,d,p$ ，如果有：

\left\{ \begin{aligned} & a\equiv b\pmod p \\ & c\equiv d\pmod p\end{aligned} \right.

则有：

a-c \equiv b-d\pmod p

a\times c \equiv b\times d\pmod p

a^c \equiv b^d\pmod p

移项和约分#

同余方程允许移项．

对于整数 $a,b,c,p$ ，如果有：

a\equiv b+c\pmod p

则有：

a-c \equiv b\pmod p

证明：

\begin{align*} a&\equiv b+c\pmod p\\ a-c&\equiv b+c-c\pmod p\\ a-c&\equiv b\pmod p \end{align*}

同余方程允许约分．

对于整数 $a,b,p$ ，如果有：

a\equiv b\pmod p

且 $c$ 是 $a, b, p$ 的公因数，则有：

\frac{a}{c} \equiv \frac{b}{c}\pmod {\frac{p}{c}}

证明：

由已知条件可得：

\left\{ \begin{aligned} & k_1p+n=a \\ & k_2p+n=b \end{aligned} \right.

其中，

n,k_1,k_2\in\mathbb{Z}

所以：

\begin{aligned} \frac{a}{c}\bmod \frac{p}{c}&=\frac{k_1p+n}{c}\bmod \frac{p}{c}\\ &=(k_1\frac{p}{c}+\frac{n}{c})\bmod \frac{p}{c}\\ &=\frac{n}{c} \end{aligned}

同理可证，

\frac{b}{c}\bmod \frac{p}{c}=\frac{n}{c}

所以：

\frac{a}{c} \equiv \frac{b}{c}\pmod {\frac{p}{c}}

逆元#

若 $ab\equiv 1\pmod p$ ，且 $a,b,p \in \mathbb{Z}$ ，则称 $a$ 和 $b$ 互为模 $p$ 下的逆元， $a$ 的逆元可以记作 $a^{-1}$ ．若 $a$ 和 $p$ 不互质，则不存在 $a^{-1}$ ．

特别的，1 的逆元总是 1．

那么，逆元在 OI 中有什么用呢？

众所周知，取模有以下性质：

a \bmod p + b = (a + b) \bmod p

a \bmod p - b = (a - b) \bmod p

a \bmod p \times b = (a \times b) \bmod p

但取模有以下性质吗？

a \bmod p \div b \overset{\text{?}}{=} (a \div b) \bmod p

随便取个特殊值，当 $a$ 为 15， $b$ 为 5， $p$ 为 10 时， $a \bmod p \div b = 1$ ， $(a \div b) \bmod p = 3$ ，显然不成立．

那该怎么办呢？又不可能在程序的最后才取模，那样早报 long long 了．

在取模运算中，除以一个数等于乘它的逆元．故拥有以下性质：

(a \div b) \bmod p = a \bmod p \times b^{-1}

除法性质#

对于整数 $a,b,c$ ，如果有：

\begin{aligned} & ac\equiv bc\pmod p\end{aligned}

则有：

a \equiv b\pmod p

证明：

\begin{aligned} ac&\equiv bc\pmod p\\ ac\cdot c^{-1}&\equiv bc\cdot c^{-1} \pmod p\\ a &\equiv b\pmod p \end{aligned}

剩余类和完全剩余系#

对于正整数 $p$ ，全部整数可以分为 $p$ 个集合，令其为 $K_0,K_1,K_2,\cdots,K_{p-1}$ ，其中，整数 $n$ 和其所在的集合 $K_i$ 所满足的条件为：

n\equiv i\pmod p

则称 $K_0,K_1,K_2,\cdots,K_{p-1}$ 为模 $p$ 的剩余类．

对于一个集合 $s$ ，如果集合中有 $p$ 个元素，且每一个元素和其他元素都不在同一个模 $p$ 的剩余类中，则称这个集合 $s$ 是模 $p$ 的完全剩余系．模 $p$ 的完全剩余系有无数个．

费马小定理#

如果 $p$ 是一个质数，而整数 $a$ 和 $p$ 互质，则有：

a^{p-1}\equiv 1\pmod p

证明：

假定模 $p$ 的完全剩余系 $s=\{0, 1, 2, \cdots, p-1\}$ ，不妨将 $s$ 中的每一项都乘 $a\in\mathbb{Z}$ ， $a\neq 0$ ，得到一个新的集合 $s'=\{0,a,2a,\cdots,(p-1)a\}$ ．

引理：

s'

是一个新的关于模

p

的完全剩余系．

假设 $s'$ 中存在两个元素 $ai$ 和 $aj$ ，他们符合： $ai\equiv aj\pmod p,i\neq j$

所以，

\begin{aligned} ai\equiv aj\pmod p \Rightarrow p \mid (ai-aj) \Rightarrow p \mid a(i-j) \end{aligned}

由于 $p$ 与 $a$ 互质，所以 $p \mid i-j$ ，又因为 $0\leq i,j\lt p$

所以不存在这样的 $i,j$ 使得 $p \mid i-j$ ，这与假设矛盾．

得证．

我们现在将模 $p$ 为 0 的一项删去，即 $s$ 和 $s'$ 中的 $0$ ．

我们可以知道，在删去 $0$ 后， $s$ 的各项之积 $T$ 为：

\begin{aligned} T &=1\times 2\cdots \times(p-1)\\ &=(p-1)! \end{aligned}

$s'$ 的各项之积 $T'$ 为：

\begin{aligned} T'&=a\cdot 2a\cdots ({p-1})a\\ &=a^{p-1}(p-1)! \end{aligned}

可推得：

\begin{aligned} T \bmod p&=(p-1)!\bmod p\\ T'\bmod p&=(a\bmod p)(2a\bmod p)\cdots[(p-1)a\bmod p]\bmod p\\ &=k_1k_2k_3\cdots k_{p-1}\bmod p\\ k_i\in\mathbb{Z},&0\lt k_i\lt p \end{aligned}

又由于 $s'$ 是模 $p$ 的完全剩余系，所以每一个 $k_i$ 都是一个 $[1,p-1]$ 之间的值（注意， $k_i$ 的值不一定是 $i$ ），且两两互不相同．

所以，

\begin{aligned} T'\bmod p&=k_1k_2k_3\cdots k_{p-1}\bmod p\\ &=1\times 2\times\cdots\times (p-1)\bmod p\\ &=(p-1)!\bmod p\\ &=T\bmod p \end{aligned}

由此可得， $T'\equiv T\pmod p$

所以：

\begin{aligned} T'&\equiv T\pmod p\\ a^{p-1}(p-1)!&\equiv (p-1)!\pmod p \end{aligned}

令 $(p-1)!$ 的逆元为 $n$ ，所以：

\begin{aligned} a^{p-1}(p-1)!&\equiv (p-1)!\pmod p\\ a^{p-1}(p-1)!n&\equiv (p-1)!n\pmod p\\ a^{p-1}&\equiv 1\pmod p\\ \end{aligned}

得证．

利用费马小定理求逆元#

\begin{aligned} a^{p-1}&\equiv 1\pmod p\\ a\cdot a^{p-2}&\equiv 1\pmod p\\ \end{aligned}

所以， $a$ 的逆元是 $a^{p-2}$ ．在实战中，可以使用快速幂在 $O(\log p)$ 的时间复杂度之内解决．

线性求逆元#

费马小定理固然可以求解逆元，但如果现在想要知道从 1 开始到 n 中每个数的逆元，就需要 $O(n\log p)$ 的时间复杂度．能不能在 $O(n)$ 中解决呢？

假设我们现在要求解 $i$ 在模 $p$ 意义下的逆元．

必然存在正整数 $k, r$ 满足 $p = k\times i + r$ ，且 $0\lt r \lt i$ ．

则此时， $k = \lfloor \frac{p}{i} \rfloor$ ， $r=p \bmod i$ ．

\begin{aligned} p&=k\times i+r\\ k\times i + r &\equiv 0 \pmod p\\ \end{aligned}

两边同时乘 $inv[i] \times inv[r]$ ，得

\begin{aligned} k\times inv[r] + inv[i] &\equiv 0 \pmod p\\ inv[i] &\equiv -k\times inv[r] \pmod p\\ \end{aligned}

由于 $k = \lfloor \frac{p}{i} \rfloor$ ， $r=p \bmod i$ ，且负数取模可化为正数，最终得到常用形式（取模运算优先级和乘除同级）：

\begin{aligned} inv[i] &\equiv p -\lfloor \frac{p}{i} \rfloor\times inv[p \bmod i] \pmod p\\ inv[i] &= p -\lfloor \frac{p}{i} \rfloor\times inv[p \bmod i] \bmod p\\ \end{aligned}

口诀：商乘余逆，主模相减（上秤鱼腻，煮馍想剪）

想象你正在制作鱼汤泡馍，你将一条鱼抱到秤上，想称一称这条鱼有多重，可是鱼滑腻，你拿不起来．拿起鱼来，放进锅中，你又把馍放到锅里去煮，馍煮得太烫了，于是你想用剪刀把它夹出来剪开．

关键代码：

1
const int p = 1000000007; // 一个常见的大质数
2
int n = 10; // 求 1...n 的逆元
3

4
vector<long long> inv(n + 1);
5
inv[1] = 1; // 1 的逆元是 1
6

7
for (int i = 2; i <= n; ++i) {
8
  inv[i] = p - (p / i) * inv[p % i] % p;
9
}

音乐

音乐

定义#

性质#

同余的基本性质#

加法性质#

加法性质的引申性质#

移项和约分#

逆元#

除法性质#

剩余类和完全剩余系#

费马小定理#

利用费马小定理求逆元#

线性求逆元#

文章分享

音乐

取模与逆元

定义#

性质#

同余的基本性质#

加法性质#

加法性质的引申性质#

移项和约分#

逆元#

除法性质#

剩余类和完全剩余系#

费马小定理#

利用费马小定理求逆元#

线性求逆元#

文章分享