数论导论
快速幂
求 $a^b\bmod p$ 的结果。
我们可以构造如下算法：
$ab=\begin{cases}(a)^2 &\texttt{b is even}\a(a{\frac{b-1}2})2&\texttt{b is odd}\end{cases}$
每次 $b$ 会减半，所以时间复杂度 $O(\log b)$。
模板题P1226 【模板】快速幂||取余运算
龟速乘
求 $ab\bmod p$ 的结果。
$a,b,p$ 都是 $10^{18}$ 级别。
我们同样可以构造类似的算法。
时间复杂度 $O(\log b)$。
整除
$a|b\Leftrightarrow b=ka (k\in\Z)$。
素数
$p\in\mathbf{P}\Leftrightarrow{x\mid x|p}={1,p}$。
可以证明有无穷多个素数。
还可以证明 $n$ 以内的素数个数 $\pi(n)\sim\frac n{\ln{n}}$。
埃氏筛
每个数筛掉倍数。一个优化就是只筛素数。
时间复杂度 $O(n\log\log{n})$。
int ntp[maxn];void ass() {for (int i = 2; i < maxn; i++) {if (ntp[i]) continue;for (int j = i + i; j < maxn; j += i)ntp[j] = 1;}
}
欧拉筛
还是筛倍数，但是让每个数只被最小的质因子筛到。
每个数都去和之前算出来的素数相乘来标记 ntp，
如果当前素数超过了当前数的最小质因子了，那就不再用后面的素数更新了。
时间复杂度 $O(n)$。
int tot;
int ntp[maxn];
int prm[maxn];void ols() {for (int i = 2; i < maxn; i++) {if (!ntp[i]) prm[++tot] = i;for (int j = 1; j <= tot && prm[j] * i < maxn; j++) {ntp[i * prm[j]] = 1;if (i % prm[j] == 0)break;}}
}
模板题 P3383 【模板】线性筛素数
快速 $\pi(n)$ 算法
计 $p_m(n)$ 表示不包含 $prm_1,prm_2\dots prm_m$ 的因子的数的个数。
显然 $p_m(n)=p_{m-1}(n)-p_{m-1}(\lfloor\frac n{prm_m}\rfloor)$。
可以 $O(m\sqrt n)$ 计算。
让 $m$ 满足 $prm_m^3>n$，那么 $p_m(n)$ 就计算了素数和由两个素数乘起来的合数的个数。
第二个东西显然可以 $O(\sqrt n)$ 搞掉。
注意到 $m\sim \frac{n^{\frac13}}{\log n}$，所以总复杂度就是 $O(\frac{n^{\frac56}}{\log n})$。
实际上 $m$ 还可以取 $prm_m^4>n$，后面还是可以搞，可以做到 $O(\frac{n^{\frac34}}{\log n})$ 的复杂度。
最大公约数
$x=\gcd(a,b)\Leftrightarrow \forall_{y|a,b}{y|x}$。
辗转相减法
$\gcd(a,b)=\gcd(b,b-a)$。
证明：
设 $k=\gcd(a,b)$，那么 $a=kp$，$b=kq$，所以 $b-a=k(q-p)$，$b=kq$，那么有 $\gcd(a,b)|\gcd(b-a,b)$。
反之也有 $\gcd(b-a,b)|\gcd(a,b)$。
所以 $\gcd(a,b)=\gcd(b-a,a)$。
辗转相除法
直接多次应用上法可以得出
$\gcd(a,b)=\gcd(b,a \bmod b)$。
容易发现 $a\bmod b\le\frac a2$。
所以每一次 $a,b$ 中有一个会减半，总复杂度为 $O(\log{\min(a,b)})$。
exgcd
求解方程 $ax+by=1$ 的一组解。
考虑 gcd 的过程。
假如已经有了这样一组解：$bx'+(a\bmod b)y'=1$，
那我们可以构造出一组解：
$\begin{cases}x=y'\y=x'-y'\lfloor\frac ab\rfloor\end{cases}$
满足 $ax+by=1$。
时间复杂度不变。
模板题 P5656 【模板】二元一次不定方程 (exgcd)
练习题 P1516 青蛙的约会
同余
$a\equiv b\pmod p\Leftrightarrow a\bmod p=b\bmod p$。
容易发现有如下性质。
-
$a\equiv b\pmod p\Leftrightarrow a+c\equiv b+c\pmod p$
-
$a\equiv b\pmod p\Rightarrow ac\equiv bc\pmod p$
-
$a\equiv b\pmod p\Rightarrow ac\equiv bc\pmod {pc}$
乘法逆元
$a^{-1}a\equiv1\pmod p$
当 $\gcd(a,p)=1$ 且 $p$ 是质数时，由费马小定理 $a^p\equiv a\pmod p$，可以得出 $a^{p-2}a\equiv1\pmod p$。
证明：多项式定理。
如果 $p$ 不是质数，也可以看成是一个方程 $a^{-1}a+bp=1$，用拓欧来解即可。
模板题 P3811 【模板】乘法逆元
线性逆元
要求多个数的逆元。
先求出前缀积，再求所有数的积的逆元，再一次往前乘就可以了。
时间复杂度 $O(n+\log p)$。
模板题 P5431 【模板】乘法逆元 2
欧拉定理
$a^{\varphi(p)}\equiv 1\pmod p$
$(\gcd(a,p)=1)$
证明：
考虑 $\varphi(p)$ 计数到的所有数 ${a_1,a_2,a_3\dots a_{\varphi(p)}}$，显然互不相同且与 $p$ 互质。
注意到 $ka_1,ka_2,ka_3\dots ka_{\varphi(p)}$ 仍然满足上一条性质。
显然这两个集合模意义下就必然是相同的了。
那么两个集合中的数之积就应相等，$\prod\limits_{i=1}^{\varphi(p)}{a_i}\equiv k{\varphi(p)}\prod\limits_{i=1}\pmod p$。
所以就能得到 $k^{\varphi(p)}\equiv1\pmod p$ 了。
拓展欧拉定理
当 $k>\varphi(p)$ 的时候有 $a^k\equiv a^{k\bmod\varphi(p)+\varphi(p)}\pmod p$。
例题 P4139 P4139 上帝与集合的正确用法
求 $2{2{2^{\dots}}}\bmod p$。
保证 $p$ 是质数。
Solution
直接暴力拓欧，不会递归超过 $\log$ 层。
时间复杂度 $O(\log^2p)$。
中国剩余定理
求一个同余方程组的解集：
$\begin{cases}x\equiv a_1\pmod{m_1}\x\equiv a_2\pmod{m_2}\x\equiv a_3\pmod{m_3}\\dots\x\equiv a_n\pmod{m_n}\end{cases}$
保证 $m_1,m_2,m_3\dots m_n$ 两两互质。
设 $M=\prod\limits_{i=1}^n{m_i},p_i=\frac M{m_i},q_i\equiv p_i^{-1}\pmod{m_i}$，那么就有
$x\equiv\sum\limits_{i=1}^{n}{a_ip_iq_i}\pmod M$
这就是该方程组的解集。
模板题 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
练习 P2480 [SDOI2010]古代猪文(需要前置知识 Lucas)