前言

基础数论知识。

original edition 2023.3.29。

upd 2023.6.19：为明天听 zyw 大佬讲课复习，并优化 Latex。

upd 2023.6.20：新增扩展欧几里得，同余最短路，逆元，中国剩余定理。

知识点

线性筛

原理：让每个数被它最小质因数筛一次。
若 $i\bmod prime[j]=0$，则 $i\cdot prime[j+k],k\geq0$ 的最小质因数为 $prime[j]$ 而非 $prime[j+k]$。此时筛完 break。

代码实现：

for(int i=2;i<=n;i++)
{
	if(!v[i]) p[++k]=i;
	for(int j=1;j<=k&&i*p[j]<=n;j++)
  	{
  		v[i*p[j]]=1;
	  	if(i%p[j]==0) break;
	}
}

唯一分解定理

$N=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$。
$N$ 正约数个数：$\prod_{i=1}^{m}(c_{i}+1)$。
$N$ 正约数和： $\prod_{i=1}^{m}(\sum_{j=0}^{c_{i}}(p_{i})^j)$。

最大公约数

$a\leq b,\gcd(a,b)=\gcd(b,b-a)=\gcd(a,b-a)$。
$b\neq 0,\gcd(a,b)=\gcd(b,a\bmod b)$。

证明:

$a<b,\gcd(b,a\bmod b)=\gcd(b,a)$

$a\geq b$，设 $a=q\cdot b+r,0\leq r<b,r=a\bmod b $

设 $d\mid a,d\mid b$，$d$ 为 $a,b$ 公约数集合任一数。则 $d\mid (a-qb)$ 即 $d\mid r$。所以 $b,a\bmod b$ >和 $a,b$ 有相同公约数集合，故最大公约数相同。

tip : 设 $a=k_{1}d,b=k_{2}d$，则 $(a-qb)=(k_{1}-k_{2}q)d$，必然整除 $d$

$\gcd(a,b) \cdot \operatorname{lcm}(a,b)=a \cdot b$

欧拉函数

$\varphi(n)$ 定义：$1\sim N $ 中与 $N$ 互质的数的个数。
根据唯一分解定理 $N=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$，$\varphi(N)=N\times \prod_{i=1}^{m}(1-\frac{1}{p_{i}})$

证明：

对于每个质因子 $p$，$1\sim N$ 中均有 $\frac{N}{p}$ 个倍数。

对于每几个质因子（这里举两个） $p_{i},p_{j}$，$p_{i}p_{j}$ 的倍数被减了两次，需要加回来一次，即 $N-\frac{N}>{p_{i}}-\frac{N}{p_{j}}+\frac{N}{p_{i}p_{j}}=N(1-\frac{1}{p_{i}})(1-\frac{1}{p_{j}})$（容斥原理）

欧拉函数性质（省略版）

(1). $\forall n>1$，$1\sim n$ 中与 $n$ 互质的数的和为 $n\cdot \varphi(n)/2$。

(2). 欧拉函数是积性函数。积性函数性质：$f(ab)=f(a)\cdot f(b)$，$a,b$互质。

(3). 若 $p$ 是质数，$p\mid n,p^2\mid n$，则 $\varphi(n)=\varphi(n/p)\cdot p$。

(4). 若 $p$ 是质数，$p\mid n,p^2\nmid n$，则 $\varphi(n)=\varphi(n/p)\cdot (p-1)$。

tip：$\varphi(p)=p-1$，$p$ 为质数（除了 $p$ 的倍数，肯定 $1\sim p-1$ 都与 $p$ 互质）。

证明：

(1). 设 $x$ 与 $n$ 互质，又 $\gcd(n,x)=\gcd(n,n-x)=1$ 所以与 $n$ 互质的数 $x,n-x$ 成对出现，平均值为 $n/>2$，有 $\varphi(n)$ 个。

(2). 请自行用公式计算证明。

(3). 设 $n=kp^2$，则 $n/p=kp$，显然 $n,n/p$ 质因子相同，代入公式算即可。

(4). $p^2 \nmid n$ 则 $p \nmid n/p$，故 $n/p$ 不是 $p$ 倍数，$p$ 又为质数，二者肯定互质，利用积性函数性计算即可。

tip：根据(3)，(4)，可以线性求欧拉函数（很简单，直接手推一波啥事没有）。

欧拉定理及扩展

若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1\pmod n$。($n$ 为质数你猜猜是啥)
若正整数 $a,n$ 互质，则对于任意正整数 $b$，有 $a^b \equiv a^{b \bmod \varphi(n)} \pmod n$
若 $a,n$ 不一定互质，且 $b>\varphi(n)$，有 $a^b\equiv a^{b \bmod \varphi(n)+\varphi(n)} \pmod n$

tip : 是费马小定理。

证明：

（1）先引入两个概念，同余类和剩余系。

对于 $\forall a \in [0,m-1]$，集合 $\{a+km\}$（$k$ 为整数）的所有数模 $m$ 余数都是 $a$，则称该集合为一个模 $m$ 的同余类，简记为 $\overline{a}$。

$m$ 的完全剩余系：一共有 $m$ 个，分别为 $\overline{0},\overline{1},\overline{2},...,\overline{m-1}$。

$m$ 的简化剩余系：一共有 $\varphi(m)$ 个，即 $1\sim m$ 中与 $m$ 互质的个数。

例如：模 $10$ 的简化剩余系为 $\{\overline{1},\overline{3},\overline{7},\overline{9} \}$。

此外，简化剩余系关于模 $m$ 乘法封闭（集合内两个数相乘，还是在集合内）。

因为 $a,b$ 与 $m$ 互质，则 $a\times b$ 也与 $m$ 互质，$a\times b \ \ mod \ \ m$ 也与 $m$ 互质。

（2）接下来证明欧拉定理。

设 $n$ 的简化剩余系为 $\{\overline{a_{1}},\overline{a_{2}},...,\overline{a_{\varphi(n)}} \}$。

$\{\overline{aa_{1}},\overline{aa_{2}},...,\overline{aa_{\varphi(n)}} \}$ 也可表示为 $n$ 的简化剩余系。（A）

证明（A）：

由于 $a,n$互质和简化剩余系的乘法封闭，故 $\overline{aa_{i}}$ 也在简化剩余系集合中。我们假设 $aa_{i}\equiv aa_{j}(mod\ n),\ i\neq j$，根据同余性质，两边同时除以 $a$ 仍然成立，再根据 $a_{i},a_{j}<n$，故 $a_{i} = a_{j}$。在简化剩余系中，显然不存在 $a_{i}=a_{j}$，故原结论成立。

证毕（A）

综上： $a^{\varphi(n)}a_{1}a_{2}...a_{\varphi(n)}\equiv (aa_{1})(aa_{2})...(aa_{\varphi(n)})\equiv a_{1}a_{2}...a_{\varphi(n)}\pmod n$，

因此 $a^{\varphi(n)} \equiv 1\pmod n$

证明：

设 $b=q\cdot \varphi(n)+r,0\leq r < \varphi(n)$，

则 $a^b \equiv a^{q\cdot \varphi(n)+r}\equiv (a^{\varphi(n)})^q\cdot a^r \equiv 1\cdot a^r \equiv a^{b\bmod \varphi(n)}\pmod n$

tip ：注意第一条定理，和 $r$ 等于什么

证明：

先引入一个结论：若 $n_{1},n_{2}$ 互质，$x\equiv y\pmod {n_1},x\equiv y \pmod {n_2}$，则$x \equiv y \pmod {n_1 n_2}$。

这个移项后发现 $x-y$ 是 $\operatorname{lcm}(n_{1},n_{2})$ 的倍数，然后 $\operatorname{lcm}(n_{1},n_{2})=n_{1}n_{2}$，故成立。

受这个启发，我们先把 $n$ 质因数分解为 $n=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{m}^{c_{m}}$。显然，任两个 $p_{i}^{c_{i}}$ 互质。如此，我们只需要证明 $\ a^b\equiv a^{b \bmod \varphi(n)+\varphi(n)} \pmod {p_i^{c_i}}$
，再把它们乘起来，原式得证。

接下来，我们分析如何证上面的式子。

若 $\gcd(a,p_{i}^{c_{i}})=1$，显然符合欧拉定理 1，2 条结论，故可以证明，这里不多赘述。

若 $\gcd(a,p_{i}^{c_{i}})\neq 1$，则可设 $a=k\cdot p_{i}$。（显然，$a$ 是 $p_{i}$ 的倍数，毕竟 $p_{i}$ 是质数嘛）

由于 $\varphi(p_{i}^{c_{i}})=p_{i}^{c_{i}} - \frac{p_{i}^{c_{i}}}{p_{i}}=p_{i}^{c_{i-1}}\cdot (p_{i}-1)\geq p_{i}^{c_{i-1}} \geq 2^{c_{i}-1} \geq c_{i}$

所以 $b\geq \varphi(n) \geq \varphi(p_{i}^{c_{i}}) \geq c_{i}$

因此 $p_{i}^{c_{i}}$ 是 $\ a^b$ 和 $\ a^{b\bmod \varphi(n)+\varphi(n)}$ 的因数，余数均为 $0$，故得证。

tip 1：关于 $\varphi(p_{i}^{c_{i}})$ 的求法，我们考虑只有 $p_{i}$ 的倍数和 $p_{i}^{c_{i}}$ 不互质，减去即可。

tip 2：不等式里"忽视" $p(i-1)$ 和把 $p_{i}$ 放缩为 $2$ 的理由：$p$ 是质数，大于等于 2。

tip 3：如果不理解因数，注意 $a=k\cdot p_{i}$，结合不等式，次方后必定是包含 $p_{i}^{c_{i}}$ 的。

扩展欧几里得

裴蜀定理：对于任意整数 $a,b$，存在一对整数 $x,y$，满足 $ax+by=gcd(a,b)$。

证明：

根据 $\gcd(a,b)=\gcd(b,a \bmod b)$，在最后 $b=0$ 时，显然有 $x=1,y=0$ 满足 $a\cdot 1+b\cdot 0=gcd(a,0)$

设当前 $ax'+by'=\gcd(a,b)=bx+(a \bmod b)y=bx+(a-b\lfloor a/b \rfloor)y=ay+b(x-\lfloor a/b \rfloor y)$

故 $x'=y,y'=x-\lfloor a/b \rfloor y$。如此递归便能构造。

此过程还算了上述方程的一组特解，该算法为扩展欧几里得算法。代码实现：

void exgcd(int a,int b,int &x,int &y,int &d)
{
    if(b==0) return x=1,y=0,d=a,void();
    exgcd(b,a%b,x,y,d);
    int _x=x;x=y,y=_x-a/b*y;
}

求 $ax+by=c$ 的整数解。

先判是否有解。设 $d=\gcd(a,b)$，有解当且仅当 $d\mid c$。

特解：用 exgcd 求出方程 $ax+by=d$ 的特解 $x_0,y_0$，再同时乘上 $c/d$，就得到原方程的特解 $x_1,y_1$。

通解：$x=x_1+\frac{b}{d}k,y=y_1-k\frac{a}{d},k\in \mathbb{Z}$。

过程：假设将 $x_1$ 扩大为 $x_1+p$，~~观察法~~发现 $y_1$ 需要减小，设减小为 $y_1-q$。（$p,q \in \mathbb{N}^+$，事实上是我们希望 $p,q$ 为正整数）

解 $\begin{cases}ax_1+by_1=c \\ a(x1+p)+b(y_1-q)=c \end{cases}$

得：$p=\frac{bq}{a},q=\frac{ap}{b}$，又 $p,q \in \mathbb{N}^+$，所以 $a \mid bq,b \mid ap$。

令 $p,q$ 最小（也就是最小偏差量），就可以表示通解了。不难得出 $bq_{min}=\operatorname{lcm}(a,b)=\frac{ab}{d}$，$p$ 同理，得 $p_{min}=\frac{b}{d},q_{min}=\frac{a}{d}$。

求解线性同余方程 $ax \equiv b \pmod n$。

移项得 $ax-b \equiv 0 \pmod n$，即 $ax-b$ 使 $n$ 的倍数。假设为 $-y$ 倍，则 $ax+ny=b$。就是刚刚的不定方程。

同余数最短路

一般用来解决用若干整数使用任意次拼数这类的问题。

显然可以用完全背包来解决，复杂度 $O(nV)$，$V$ 为背包体积。

若用 dijkstra 求解最短路，设这若干整数绝对值最小的为 $m$，复杂度为 $O(n\log (n+m))$。

假设我们用 $a_1,a_2,...,a_n$ 拼数。

选定 $a_1$ （可以选任意数）为模数。考虑 $a_1$ 的同余类 $\overline{x}$，若其中一个数 $t$ 能被 $a_2,a_3,...,a_n$ 凑出，则 $\overline{x}$ 中大于等于 $t$ 的数都能被凑出。

由此，考虑 $a_1$ 个同余类中最小能被凑出的数，设为 $d$，则此同余类在 $[0,r]$ 中能凑出的数的个数为 $\lfloor \frac{r-d}{a_1} \rfloor$ 。

问题转化为如何求每个同余类最小能被凑出的数。

这可以转化为一个图论问题。对每个同余类建一个节点，向其加 $a_i,i\in[2,n]$ 到达的同余类分别连边，边权为 $a_i$。那么问题就转化为了跑最短路。

代码实现：

for(int i=0;i<a[1];i++)
	for(int j=2;j<=n;j++)
		G[i].emplace_back((i+a[j])%a[1],a[j]);
dijkstra();// spfa or other algorithms
// 假设要求统计能凑出 [l,r] 中多少不同的数。
ll ans=0;
for(int i=0;i<a[1];i++)
{
	if(r>=d[i]) ans+=(r-d[i])/a[1]+1;
	if(l-1>=d[i]) ans-=(l-1-d[i])/a[1]+1;
}

逆元

实用主义定义：考虑一个分数 $\frac{a}{b}$ 对 $p$ 如何进行取模运算。就是乘上 $b$ 关于 $p$ 的逆元。

$O(\log p)$ 求逆元：

设逆元为 $x$，根据定义，$\frac{a}{b} \equiv ax$。即 $x \cdot b \equiv 1 \pmod p$。
若 $p$ 为质数，根据费马小定理 $b^{p-1} \equiv 1 \pmod p$，得 $x=b^{p-2}$。
若 $b,p$ 互质，则用 exgcd 求解上述线性同余方程（所以逆元可能不存在）。

线性求逆元（显然逆元得是个质数）：

设当前要求 $i$ 的逆元，$p=q \cdot i+r$，即 $q \cdot i+r \equiv 0 \pmod p$。
同时乘 $i^{-1},r^{-1}$ ：$q \cdot r^{-1}+i^{-1} \equiv 0 \pmod p$。
$i^{-1} \equiv -q \cdot r^{-1} \pmod p$。
为了方便，让逆元非负，右边加上 $p\cdot r^{-1}$（此数为 $p$ 的倍数，模 $p$ 意义下显然允许），得最终式子：
$i^{-1} \equiv (p-p/i) \cdot (p \bmod i)^{-1}$。

inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=1ll*(p-p/i)*inv[p%i]%p;

线性求阶乘逆元：

$(n!)^{-1} \equiv [(n+1)!]^{-1} \cdot (n+1) \pmod p$

inv[n]=qpow(fac[n],p-2);
for(int i=n-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%p;

中国剩余定理及扩展

设 $p_1,p_2,...,p_n$ 是两两互质的整数，$p=\prod\limits_{i=1}^{n}p_i,P_i=p/p_i$，$t_i$ 是线性同余方程 $P_it_i \equiv 1 \pmod {p_i}$ 的一个解，则对于方程组

$\begin{cases} x \equiv a_1 \pmod {p_1} \\ x \equiv a_2 \pmod {p_2} \\...\\ x \equiv a_n \pmod {p_n}\end{cases}$

有整数解 $x=\sum\limits_{i=1}^{n}a_iP_it_i$。

证明：$P_i$ 是除 $p_i$ 之外所有模数的倍数，那么最终 $x$ 加上 $P_i$ 的倍数就不影响其余方程。又因为 $a_iP_it_i \equiv a_i \pmod {p_i}$，满足当前方程组，所以代入 $x$，原方程组成立。

若要求最小正整数解，只需每步对 $ans=(ans \bmod p+p) \bmod p$，使 $ans$ 落在 $0 \sim p-1$ 范围内，就是最小正整数解。

代码实现：

void CRT()
{
	ll p=1,ans=0;
	for(int i=1;i<=n;i++) p*=p[i];
	for(int i=1;i<=n;i++)
	{
		int P=p/p[i],t,y;
		exgcd(P,p[i],t,y);
		ans+=1ll*a[i]*P*t;
	}
}

题外话

机房大佬叶师傅跟我提到过可以用 CRT 还原被取模数。

但我懒，没试过。

JZTXT

基础数论知识

前言

知识点

线性筛

唯一分解定理

最大公约数

欧拉函数

欧拉定理及扩展

证明：

扩展欧几里得

同余数最短路

逆元

中国剩余定理及扩展