前言

前段时间在补提高大纲，补完之后这篇博客用来记录梳理复盘提高大纲里数论的一些知识点，有错误欢迎批判捏。

欧拉函数

定义

\(\varphi(n)\) 表示小于等于 \(n\) 中与 \(n\) 互质的数的个数，即 \(\varphi(n)= \sum ^n _{d=1} [\gcd(d,n)=1]\).

性质

1. 积性函数

根据这一条性质，我们可以用线性筛法来筛出欧拉函数。

2. 若 \(n=p^k\)，其中 \(p\) 为一个质数，则 \(\varphi(n)=p^k-p^{k-1}\).

证明

根据定义可知，更详细一点说，若存在一个数 \(x\) 满足 \(\gcd(x,n)\not=1\)，那么一定有 \(p|x\)，因此我们可以稍微用一点容斥的思想，\(p^k\) 即是全集，而 \(p^{k-1}\) 则是不符合 \(\gcd(x,n)=1\) 的 \(x\) 的数量，相减即可得出答案。

3. 由唯一分解定理可得，\(n=\prod_{i=1}^s p_i^{k_i}\)，其中 \(p\) 为素数，那么可得 \(\varphi(n)=n \times \prod^s_{i=1}\frac{p_i-1}{p_i}\).

证明

由性质一、性质二可得:

根据这一条，我们可以单点求欧拉函数，在推柿子的时候也经常用到，算是比较重要的一条性质。

ll phi(ll x) {
	ll res=x;
	for(ll i=2;i*i<=x;i++) {
		if(!(x%i)) {
			res=res/i*(i-1);
			while(!(x%i)) x/=i;
		}
	}
	if(x>1) res=res/x*(x-1);
	return res;
}

4. \(n=\sum_{d|n} \varphi(d)\)

证明

若 \(\gcd(k,n)=d\)，那么可以得到 \(\gcd(\frac{k}{d},\frac{n}{d})=1\)，我们把这个结论称为结论一。

设 \(f(x)\) 表示 \(\gcd(k,n)=x\) 的数的个数，那么 \(n=\sum^n_{i=1}f(i)\).

由结论一可得 \(n=\sum^n_{i=1}\varphi(\frac{n}{i})\) 即 \(n=\sum_{d|n}\varphi(\frac{n}{d})\).

因为 \(d\) 与 \(\frac{n}{d}\) 具有对称性，所以 \(n=\sum_{d|n} \varphi(d)\).

这一条目前没遇到什么应用，不过了解一下也是好的。

一位大佬说可用于欧拉反演，但是我不会（逃，等会了再扩充。

欧拉定理

定义

若 \(\gcd(a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod{m}\).

证明

设 \(r_1,r_2 \dots r_{\varphi(m)}\) 为模 \(m\) 意义下的一个简化剩余系，则 \(ar_1,ar_2 \dots ar_{\varphi(m)}\) 也为模 \(m\) 意义下的一个简化剩余系，所以 \(r_1r_2 \dots r_{\varphi(m)} \equiv ar_1ar_2 \dots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \dots r_{\varphi(m)} \pmod{m}\)，约分就可得 \(a^{\varphi(m)}\equiv 1\pmod{m}\).

注：

剩余类：对于同一个整数 \(n\)，其余整数模 \(n\) 后有 \(0 \sim n-1\) 共 \(n\) 种情况，其中余数相同的称为同一剩余类。

简化剩余类（完全剩余系）：在每一个剩余类中取一个数，构成的集合称为简化剩余类。

简化剩余系：从完全剩余系中取出 \(\varphi(n)\) 个与 \(n\) 互质的数所构成的集合。

费马小定理

定义

若 \(p\) 为素数，\(\gcd(a,p)=1\)，则 \(a^{p-1} \equiv 1 \pmod{p}\).

证明：

因为 \(p\) 为素数，所以 \(\varphi(p)=p-1\)，由欧拉定理可得 \(a^{\varphi(p)}\equiv 1\pmod{p}\)，故 \(a^{p-1} \equiv 1 \pmod{p}\).

费马小定理在求乘法逆元时有用。

威尔逊定理

定义

对于素数 \(p\) 有 \((p-1)! \equiv -1 \pmod{p}\).

证明

我们可以分为两种情况讨论：

1. 当 \(p=2\) 时，有 \((p-1)! = 1\)，显然有 \(1 \equiv -1 \pmod{p}\)，因此威尔逊定理在 \(p=2\) 时成立。

2. 当 \(p\) 为任意的奇素数时，\(1 \sim p-1\) 均存在逆元且唯一，对于每一个数 \(x\)，若满足 \(x \not= x^{-1}\pmod{p}\)，就可得 \(x \times x^{-1}=1\)，因此 \((p-1)! \bmod p\) 就等于逆元等于其本身即满足 \(x = x^{-1}\pmod{p}\) 的数的乘积，因为 \(p\) 为素数，所以这样的数只有 \(1\) 和 \(p-1\)，而 \((p-1) \bmod p=-1\)，威尔逊定理成立。

裴蜀定理（贝祖定理）

定义

设 \(a,b\in\mathbb{Z}\) 且 \(a,b\) 不全为 \(0\)，则 \(\exists x,y \in \mathbb{Z}\) 使 \(ax+by=\gcd(a,b)\).

证明

我们可以分为两种情况讨论。

1. 若 \(a=0\) 或 \(b=0\)，则 \(\gcd(a,b)=a\) 或 \(b\)，定理显然成立。

2. 若 \(a,b \not =0\)，因为 \(\gcd(a,b)=\gcd(-a,b)=\gcd(-a,-b)=\gcd(a,-b)\)，所以我们假设 \(a,b>0,a \geq b,\gcd(a,b)=d\).

   我们可以将等式两边同除 \(d\)，可以得到 \(a_1x+b_1y=1\)，其中 \(\gcd(a_1,b_1)=1\).
   令辗转相除法在除到互质时退出，则 \(r_n=1\)，可得：

   \[r_{n-2}=x_nr_{n-1}+1 \]

   即

   \[1=r_{n-2}-x_nr_{n-1} \]

   由 \(r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}\) 得

   \[1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} \]

   我们不断这么带入可以逐渐消去 \(r_{n-2}\dots r_1\)，可以证得 \(a_1x+b_1y=1\)，所以定理成立。

扩展欧几里得算法（exgcd）

exgcd 一般用于求解线性同余方程，而逆元也是一类特殊的线性同余方程。

基本思路

假设我们要求解不定方程 \(ax+by=\gcd(a,b)\)，其中 \(x,y\) 为未知数，那么我们可以在 \(a=\gcd(a,b),b=0\) 时得到一组解 \(x=1,y=0\)，然后通过这一组特殊解来步步回溯求出原式的解。

其中不定方程 \(ax+by=m\) 有整数解的充要条件是 \(\gcd(a,b)|m\).

如何回溯

首先根据欧几里得算法可得：

又因为 \(\gcd(b,a-\lfloor \frac{a}{b} \rfloor b)=bx_0+(a-\lfloor \frac{a}{b} \rfloor)y_0=bx_0+ay_0-\lfloor \frac{a}{b} \rfloor by_0\)

所以可以得到： \(ax+by=bx_0+ay_0-\lfloor \frac{a}{b} \rfloor by_0=ay_0+b(x_0-\lfloor \frac{a}{b} \rfloor y_0)\).

所以可以用 \(x=y_0,y=x_0-\lfloor \frac{a}{b} \rfloor y_0\) 来不断迭代更新回溯。

ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) {
		x=1,y=0;
		return a;
	}
	ll res=exgcd(b,a%b,x,y);
	ll t=x;x=y,y=t-a/b*y;
	return res;
}

解系扩展

若 \(x_0,y_0\) 为不定方程 \(ax+by=n\) 的一组解，那么该不定方程的任意解可以表示为：

其中 \(k \in \mathbb{Z}\)

而一般题目会让我们求最小整数解，那么 \(x=(x \bmod t + t) \bmod t\)，其中 \(t= \frac{b}{\gcd(a,b)}\).

模意义下的乘法逆元

定义

若一个线性同余方程 \(ax \equiv 1 \pmod{b}\)，则 \(x\) 称为 \(a\bmod b\) 的逆元，记作 \(a^{-1}\).

exgcd 求解

很明显我们可以将该线性同余方程改写为 \(ax+by=1\)，用 exgcd 求解即可。

费马小定理求解

因为 \(ax \equiv 1 \pmod{b}\)，又因为由费马小定理可得 \(ax \equiv a^{b-1} \pmod{b}\)，所以 \(x \equiv a^{b-2}\pmod{b}\)，可以用快速幂求解。

线性求逆元

可以用来求解 \(1 \sim n\) 在模 \(p\) 意义下的逆元。

首先我们有 \(1^{-1} \equiv 1 \pmod{p}\) 恒成立，故 \(1\) 的逆元为 \(1\).

接下来我们要求解 \(i^{-1}\)，我们令 \(k= \lfloor \frac{p}{i} \rfloor,j=p \bmod i\)，因为 \(p=ki+j\)，所以 \(ki+j \equiv 0 \pmod{p}\).

同余式两边同乘 \(i^{-1} \times j^{-1}\) 可得 \(kj^{-1}+i^{-1} \equiv 0 \pmod{p}\)，移项得 \(i^{-1} \equiv -kj^{-1} \pmod{p}\)，即 \(i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor(p \bmod i)^{-1} \pmod{p}\).

综上：

在代码实现时 \(-\lfloor \frac{p}{i} \rfloor\) 写作 \(p-\lfloor \frac{p}{i} \rfloor\)，防止出现负数。

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

线性求任意 \(n\) 个数的逆元

先计算 \(n\) 个数的前缀积，记作 \(s_i\)，然后计算 \(s_n\) 的逆元记作 \(sv_n\)，很明显每次乘上 \(a_i\) 就可以得到 \(a_1 \sim a_i-1\) 的积逆元，即 \(sv_{i-1}=sv_i \times a_i\)，所以 \(a_{i}^{-1}=s_{i-1}\times sv_i\)，时间复杂度 \(\Theta(n+\log p)\).

线性同余方程

定义

形如 \(ax\equiv b \pmod{n}\) 的方程称为线性同余方程，其中 \(x\) 为未知数。

逆元求解

当 \(\gcd(a,n)=1\) 时，可以计算 \(a^{-1}\)，然后方程两边同乘 \(a^{-1}\) 可得唯一解。

证明

当 \(\gcd(a,n)\not = 1\) 时，不一定有解。

设 \(d=\gcd(a,n)\)，当 \(d \nmid b\) 时无解。

若 \(d \mid b\)，则同除 \(d\) 可得 \(a'x\equiv b' \pmod{n'}\)，此时 \(\gcd(a',n')=1\)，可用逆元求解，而原方程有 \(d\) 个解，\(x_i \equiv x'+in' \pmod{n}(0 \leq i \leq d-1)\).

exgcd 求解

线性同余方程可以改写为 \(ax+ny=b\) 的形式。

中国剩余定理（CRT）

作用

可用于求解形如以下的一元线性同余方程组，其中 \(n_1,n_2,\dots,n_k\) 两两互质。

基本思路

先计算所有模数的积记作 \(n\)，对于第 \(i\) 个方程，计算 \(m_i=\frac{n}{n_i}\)，然后再计算 \(m_i^{-1}\)，计算 \(c_i=m_im_i^{-1}\)，此时不要模 \(n_i\)，方程组的唯一解为 \(x=\sum_{i=1}^k a_ic_i \pmod{n}\).

证明

当 \(i \not=j\) 时，有 \(m_j \equiv 0 \pmod{n_i}\)，故 \(c_j \equiv m_j \equiv 0 \pmod{n_i}\)，又因为 \(c_i \equiv m_i \times (m_i^{-1} \bmod n_i) \equiv 1 \pmod{n_i}\)，所以：

所以该求法的正确性得证。

for(int i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i],&b[i]);
		Mul*=a[i];
	}
	for(int i=1;i<=n;i++) {
		M[i]=Mul/a[i];
		ll x=0,y=0;
		exgcd(M[i],a[i],x,y);
		if(x<0) x+=a[i];
		ans+=(b[i]*M[i]*x);
	}