余数性质
\[ \begin{align} (a+b) \bmod n &= (a \bmod n + b \bmod n) \bmod n \\ (a \times b) \bmod n &= (a \bmod n \times b \bmod n) \bmod n \\ a^{b} \bmod n &= (a \bmod n)^b \bmod n \end{align} \]
同余
\[
\begin{cases}
\begin{align}
(a - c) &\equiv (b - d) \pmod{n} \\
(a + c) &\equiv (b + d) \pmod{n} \\
(a \times c) &\equiv (b \times d) \pmod{n}
\end{align}, a \equiv b \pmod{n} \; and \; c \equiv d \pmod{n}
\end{cases}
\]
乘法逆元
若\(a \times b \equiv 1 \pmod{p}\)，且\(a,\;p\)互质，则\(b\)就是\(a\)的乘法逆元，记作\(a^{-1}\)，也可以叫做\(a\)在\(\bmod p\)下的倒数
有了乘法逆元就可以补充性质
\[
\frac{a}{b} \bmod p = (a \times b^{-1}) \bmod p = (a \bmod p \times
b^{-1} \bmod p) \bmod p
\]
求逆元
扩展欧几里得算法
欧几里得算法：有公式\(\gcd(a,b)=\gcd(b,a \bmod b)\)，其中\(\gcd\)是最大公约数，通过辗转相除
\[ \begin{align} \gcd(a, b) &= \gcd(b, a \bmod b) \\ \gcd(b, a \bmod b) &= \gcd(a \bmod b, b \bmod (a \bmod b)) \\ &\cdots \\ \gcd(x, d) &= \gcd(d, 0) = d \end{align} \]
当得到形如\(\gcd(d, 0)\)的式子时，说明上一步中有\(x \bmod d = 0\)，最大公约数为\(d\)扩展欧几里得算法：有公式\(ax + by = \gcd(a, b)\)，\(x, \; y\)均为整数，有如下推论
\[ \begin{align} \because &\gcd(a, b) = \gcd(b, a \bmod b) = ax + by \\ &a \bmod b = a - \lfloor\frac{a}{b}\rfloor b \\ \therefore &\gcd(b, a \bmod b) = bx^{\prime} + (a \bmod b)y^{\prime} = ax + by \\ &bx^{\prime} + (a - \lfloor\frac{a}{b}\rfloor b)y^{\prime} = ay^{\prime} + b(x^{\prime} - \lfloor\frac{a}{b}\rfloor y^{\prime}) = ax + by \\ &x = y^{\prime} \\ &y = x^{\prime} - \lfloor\frac{a}{b}\rfloor y^{\prime} \end{align} \]
通过辗转相除
\[ \begin{align} ax + by &= \gcd(a, b) \\ bx^{\prime} + (a \bmod b)y^{\prime} &= \gcd(b, a \bmod b) \\ &\cdots \\ dx^{\prime \prime} + 0 \times y^{\prime \prime} &= \gcd(d, 0) = d \end{align} \qquad \therefore x^{\prime \prime} = 1 \quad y^{\prime \prime} \in \mathbb{Z} \]
根据推论往上递推最终可以求得\(ax + by = \gcd(a, b)\)中的\(x, \; y\)
\[ \begin{align} &\because a \cdot a^{-1} \equiv 1 \pmod{p} \\ &\therefore a \cdot a^{-1} + kp = 1, \; k \in \mathbb{Z} \end{align} \]
所以当\(\gcd(a, b) = 1\)，求出的\(x\)即是\(a\)在模\(b\)下的逆元费马小定理
费马小定理：若\(p\)是质数，对应任意整数\(a\)，有\(a^{p} \equiv a \pmod{p}\)
欧拉定理：若正整数\(a, \; n\)互质，则\(a^{\varphi(n)} \equiv 1 \pmod{n}\)，其中\(\varphi(n)\)为欧拉函数，表示在小于等于\(n\)的正整数中，与\(n\)互质的数的个数
费马小定理是欧拉定理的特殊情况，用费马小定理求逆元
\[ a^{p-2} \equiv a^{-1} \pmod{p} \]
用欧拉定理求逆元
\[ a^{\varphi(n)-1} \equiv a^{-1} \pmod{n} \]
快速幂
快速幂的核心在于利用二进制和位运算
计算\(a^{b}\)，首先将\(b\)用二进制展开得\(b = x_{0} + 2^{1}x_{1} + 2^{2}x_{2} \dots, \; x_{n} \in \{0, 1\}\)，由此\(a^{b} = a^{x_{0}} \cdot a^{2^{1}x_{1}} \cdot a^{2^{2}x_{2}} \dots\)
\(b\)中每有一个1，代表此位置要乘\(a^{2^{i}}\)，否则乘1（不变），另外，有\(a^{2^{i}} \cdot a^{2^{i}} = a^{2^{i + 1}}\)
def quick_pow(base, power):
res = 1
while power > 0:
if power & 1 == 1:
res *= base
base *= base
power >>= 1
return res位运算技巧
- 消去最后一个1：
x & (x - 1) - 获取最后一个1：
x & -x - 找出序列中唯一出现奇数次的数：
x1 ^ x2 ^ x3 ...