cnblogs。

前言

大部分定理的证明是参考的相关资料，因为我是菜狗 qwq，但都是在学习后自己独立写出来的。

因为写的时候是在不同时间写的，所以通读的时候会有一点割裂感。

我一开始写只是方便自己快速复习的，但是写着写着就感觉是在给别人看一样，也不重要了。

带 * 的是不知道放哪里，又感觉另开一个大章太费事，放在需要以这个大章为核心知识的地方。

有错会及时修正，后面的 BSGS 等更高级的如果考完 NOIP 后没退役就会更新。

1 数论中的基础知识

1.1 整除

1.1.1 定义

设

a,b

是整数，如果存在一个整数

c

，使得

b=ac

，则我们称为

a

整除

b

（或

b

被

a

整除），记作

a\mid b

。

1.1.2 定理

（反射性）对于所有整数 $a$ ，满足 $a \mid a$ 。
（传递性）若 $a \mid b$ ， $b \mid c$ ，则 $a \mid c$ 。
若 $a,b_1,b_2,\cdots,b_n$ 都是整数，并且 $a \mid b_i$ （ $1 \le i \le n$ ），则 $a \mid b_1c_1+b_2c_2+\cdots+b_nc_n$ 对于所有整数 $c_1,c_2,\cdots,c_n$ 成立。
若 $a,b_1,b_2,\cdots,b_n$ 都是整数，并且 $a \mid b_i$ （ $1 \le i \le n$ ），则 $a \mid b_1c_1\times b_2c_2 \times \cdots \times b_nc_n$ 对于所有整数 $c_1,c_2,\cdots,c_n$ 成立。
若 $a \mid b$ ， $a \mid b \pm c$ ，则 $a \mid c$ 。
若整数 $a,b,c,d,e$ 满足 $a \mid b-c$ ， $a \mid d-e$ ，则 $a \mid bd - ce$ 。
若 $a\mid b$ ，则对于任意整数 $c$ ，满足 $ac\mid bc$ 。若 $ac \mid bc$ ，且 $c \ne 0$ ，则 $a\mid b$ 。

1.1.3 证明

定理 1、2、7 可以从定义入手。

定理 3、4 的证明如下：

令

w_1,w_2,\cdots,w_n

为满足下列条件的整数：

\begin{aligned} \ b_1 &= a w_1 \\ \ b_2 &= a w_2 \\ &\cdots \\ \ b_n &= a w_n \end{aligned}

则有：

\begin{aligned} \ b_1 c_1 &= a w_1 c_1\\ \ b_2 c_2 &= a w_2 c_2\\ &\cdots \\ \ b_n c_n &= a w_n c_n \end{aligned}

相加/相乘得：

\begin{aligned} \sum_{i=1}^{n} b_ic_i &= \sum_{i=1}^{n} aw_ic_i \\ &=a \times \sum_{i=1}^{n} w_ic_i \\ \prod_{i=1}^{n} b_ic_i &= \prod_{i=1}^{n} aw_ic_i \\ &= a^n \times \prod_{i=1}^{n} w_ic_i \\ &= a \times a^{n-1} \prod_{i=1}^{n} w_ic_i \end{aligned}

证毕。

定理 5 证明如下：

令

w_1,w_2

为满足

b=aw_1,b+c=aw_2

的整数。

令

c=qa

，则有

b=aw_1=aw_2-qa=a(w2-q)

。

\therefore w_1=w_2-q

。

\because w_1,w_2

为整数。

\therefore q

为整数，

w_2-q

也是整数。

-c

同理，证毕。

定理 6 证明如下：

令

w_1,w_2

，为满足

b-c=aw_1,d-e=aw_2

的整数。

则有：

\begin{aligned} b &= aw_1+c \\ d &= aw_2+e \\ \\ bd &= (aw_1+c)(aw_2+e) \\ bd &= a^2w_1w_2+aw_1e+aw_2c+ce \\ bd - ce &= a^2w_1w_2+aw_1e+aw_2c\\ bd-ce &= a(aw_1w_2+w_1e+w_2c) \end{aligned}

证毕。

1.2 同余

1.2.1 定义

设

a,b,n

是整数，若

n \mid a-b

，则称

a

和

b

模

n

同余，记作：

a \equiv b \pmod {n}

1.2.2 定理

（反射性） $a \equiv a \pmod n$ 。
（对称性）若 $a \equiv b \pmod n$ ，则 $b \equiv a \pmod n$ 。
（传递性）若 $a \equiv b \pmod n$ ，且 $b \equiv c \pmod n$ ，则 $a \equiv c \pmod n$ 。
若 $a \equiv c \pmod n$ ，且 $b \equiv d \pmod n$ ，则 $a+b \equiv c+d \pmod n$ ， $ab \equiv cd \pmod n$ 。
若 $a \equiv b \pmod n$ ，则 $ac \equiv bc \pmod {nc}$ 。若 $ac \equiv bc \pmod {nc}$ ，且 $c \ne 0$ ，则 $a \equiv b \pmod n$ 。

1.2.3 证明

定理 1、2 可以从定义入手。

定理 3 证明如下：

根据定义

n \mid a-b

，

n \mid b-c

。

由整除的定理 3 可以得到：

n \mid (a-b)+(b-c) \\ n \mid a-c

证毕。

定理 4 的证明如下：

根据定义

n \mid a-c

，

n \mid b-d

。

由整除的定理 3 可以得到：

n \mid a-c+b-d \\ n \mid (a+b)-(c+d)

由整除的定理 6 可以得到：

n \mid ab - cd

证毕。

定理 5 的证明可以由整除的定理 7 得到。

1.3 数论函数

定义域为正整数，值域为复数集的子集的函数称为数论函数。

1.3.1 积性函数

对于一个数论函数

f

，若

\forall x,y \in \mathbb{N}_+

且

x

与

y

互质，都有

f(xy)=f(x)f(y)

，则称

f

为积性函数。

对于一个数论函数

f

，若

\forall x,y \in \mathbb{N}_+

，都有

f(xy)=f(x)f(y)

，则称

f

为完全积性函数。

可以看出完全积性函数一定是积性函数。

积性函数一定满足

f(1)=1

。

一些常见的积性函数：

1 函数（完全积性）： $\mathbb{1}(n)=1$ 。
幂函数（完全积性）： $id_k(n)=n^k$ 。
狄利克雷卷积单位元（完全积性）： $\varepsilon(n)= \begin{cases} 1 \;, n=1 \\ 0 \;, n \not = 1\end{cases}$ 。
欧拉函数： $\varphi(n)=$ $1 \sim n$ 中与 $n$ 互质的数的个数。
最大公因数： $\gcd_k(n) =\gcd(n,k)$ 。
除数函数： $d(n)=$ 正整数 $n$ 的正因子个数。

1.3.2 加性函数

对于一个数论函数

f

，若

\forall x,y \in \mathbb{N}_+

且

x

与

y

互质，都有

f(xy)=f(x)+f(y)

，则称

f

为加性函数。

对于一个数论函数

f

，若

\forall x,y \in \mathbb{N}_+

，都有

f(xy)=f(x)+f(y)

，则称

f

为完全加性函数。

可以看出完全加性函数一定是加性函数。

加性函数一定满足

f(1)=0

。

两个常见加性函数：

$\Omega(n) =$ 所有素因子（含重复）的总个数。（完全加性）
$\omega(n) =$ 不同素因子的个数。

例如

12=2^2 \times 3,\Omega(12)=3,\omega(12)=2

、

30=2 \times 3 \times 5, \Omega(30)=3,\omega(30)=3

。

1.4 模运算

带余除法：对于整数

a

和

b>0

，则存在唯一的整数

q,r

，满足

a=bq+r

，其中

0 \le r <b

，其中

q

为商，

r

为余数。

余数

r

用

a \bmod b

来表示。

带余除法非常重要，在很多题目中都能用带余乘法拆分得到关键步骤。

一些运算法则：

$(a+b) \bmod M = (a \bmod M + b \bmod M ) \bmod M$ 。
$(a-b) \bmod M = (a \bmod M - b \bmod M ) \bmod M$ 。
$(a \times b) \bmod M = (a \bmod M \times b \bmod M ) \bmod M$ 。

千万千万要注意除法没有类似的运算法则！！！！

关于除法的模运算详见“模意义下的乘法逆元”。

2 素数

对于正整数

p>1

，若

p

的因数只有

1

和它本身，则

p

是素数。

2.1 唯一分解定理

每个大于 $1$ 的整数都能唯一的表示成其质因数之积。

即

n=\prod p_i^{a_i}

(

p_i

为素数且

p_1<p_2<\cdots,a_i \ge 1

)。

结论比较显然，故不给出该定理的证明。

求解代码：

CPP

void decompose(int x){
	for(int i=2;i*i<=x;++i)
		while(x%i==0) ++a[i],x/=i;
	if(x) ++a[x];
}
int main(){
	int n;scanf("%d",&n);
	decompose(n);
	for(int i=1;i<=n;++i) 
		if(a[i]) printf("%d %d\n",a[i],i);
}

一个真命题： $n$ 中最多含有一个大于 $\sqrt n$ 的因子。

证明：如果存在两个大于

\sqrt n

的因子，则二者相乘大于

n

，矛盾。

2.2 费马小定理

若一个素数 $p$ ， $a$ 是与 $p$ 互质的任意整数，有 $a^{p-1} \equiv 1 \pmod p$ 。等价地， $a^p \equiv a \pmod p$ 。

对于每一个整数 $i \in [1,p)$ ，满足 $i \times a \bmod p$ 互不相同。

证明：如果存在整数

i \ne j

且

i,j \in [1,p)

，满足

i \times a \equiv j \times a \pmod p

，则

i \equiv j \pmod p

，不符合定义。

显然有：

\prod_{i=1}^{p-1} i \equiv \prod_{i=1}^{p-1} (i\times a) \equiv a^{p-1} \prod_{i=1}^{p-1}i \pmod p

根据同余的定理 5 可以得到：

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

得证费马小定理。

实际上，费马小定理是欧拉定理的一种特殊情况，后文的欧拉定理会提及。

2.3 素数筛

2.3.1 普通筛

既然是筛法，就不能一个数一个数暴力求是不是素数，这个复杂度

O(n \sqrt n)

~~妥妥 T 飞~~。

一个大于

1

的整数显然要么素数，要么是合数。

根据素数定义，一个数是素数当且仅当其因数只有

1

和它本身。

那么对于任意大于

1

的整数

i,j

，

i \times j

必定不是素数，那么它就是合数，这样就得到了时间复杂度为

O(n \log n)

普通筛：

CPP

for(int i=2;i<=n;++i){
  if(!vis[i]) prime[++tot]=i; //没有被标记合数就是素数
  for(int j=2;j*i<=n;++j)   //枚举 i 的所有倍数 i*j  
    vis[j*i]=1;         //i 的倍数必定是合数
}

2.3.2 埃氏筛

上面的筛法也太慢了，比如

12=3\times 4

，

i=3

或

i=4

时都会把

12

筛去，我们需要更快的筛法。

不难发现，根据唯一分解定理，一个合数一定会被拆成若干质因子之积。

这样就可以把质数的倍数筛出来，就可以避免前文的例子中

i=4

这样枚举合数的倍数这种纯浪费时间的情况。

时间复杂度

O(n \log \log n)

，作者不会证复杂度 qwq。

CPP

for(int i=2;i<=n;++i){
	if(!vis[i]){
		prime[++tot]=i;
		for(int j=2;j*i<=n;++j) //枚举素数的整数倍
			vis[i*j]=1;
	}
}

既然素数的（大于

1

的）整数倍是合数，那么（大于

1

的）整数的素数倍也是合数，那么就可以得到埃氏筛的另外一种形式：

CPP

for(int i=2;i<=n;++i){
	if(!vis[i]) prime[++tot]=i;
	for(int j=1;j<=tot && i*prime[j]<=n;++j)
		vis[i*prime[j]]=1;
}

2.3.3 线性筛

埃氏筛已经够优秀了，但是带个常数还是太慢了，有没有什么更加快速的筛法吗。

有的兄弟有的，线性筛的复杂度只有

O(n)

。

线性筛的代码与埃氏筛形式 2 相比只多了一行：

CPP

for(int i=2;i<=n;++i){
		if(!vis[i]) prime[++tot]=i;
		for(int j=1;j<=tot && i*prime[j]<=n;++j){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;   //神奇的一行！
		}
	}

线性筛的思想是，对于一个合数

n

，设

n

的最小质因子为

p_n

，则

n

会且仅会在

i=\frac{n}{p_n}

被筛去。

正确性是显然的，接下来证明充要性。

充分性证明（合数

n

会在

i=\frac{n}{p_n}

时被筛去）：因为

p_n

是

n

的最小质因子，所以

\frac{n}{p_n}\ge p_n

，那么在

i=\frac{n}{p_n}

时，

p_n

就已经被记录为素数了。且根据唯一分解定理，

\frac{n}{p_n}

的质因子一定大于等于

p_n

。

当

i=\frac{n}{p_n}

时，如果出现

prime[j]

还没有枚举到

p_n

就终止，那么此时

prime[j] < p_n

且

prime[j]

一定是

i=\frac{n}{p_n}

的一个质因子，这与

p_n

是

n

的最小质因子矛盾。得证。

必要性证明（合数

n

仅会在

i=\frac{n}{p_n}

时被筛去）：假设

p'

是

n

的一个质因子且

p'>p_n

，那么根据唯一分解定理，

p_n

也一定是

\frac{n}{p'}

的一个质因子，即

p_n | \frac{n}{p'}

。所以，当

i=\frac{n}{p'}

时，当

prime[j]

枚举到

p_n

，因为

p_n | \frac{n}{p'}

，此时枚举终止，也就不会被

p'

筛去。

这样，每个合数都只会被 vis[i*prime[j]]=1 标记一次，所有的数总共不会被标记超过

n

次，所以线性筛的时间复杂度为

O(n)

。

*2.3.4 线性筛求积性函数

所有的积性函数都可以用线性筛来求。

举一个线性筛求

d(n)

的例子。

既然是线性筛，就要从唯一分解和最小质因子的角度出发。

d(1)=1

是显然的。

对于

n>1

的情况，设

P(n)

是

n

的最小质因子，

K(n)

是

n

最小质因子的指数，相当于把

n

唯一分解后的

p_1

和

k_1

。

因为

d(n)

是积性函数且

\frac{n}{P(n)^{K(n)}}

与

P(n)^{K(n)}

显然互质，所以

d(n)= d(\frac{n}{P(n)^{K(n)}}) \times d(P(n)^{K(n)}) = d(\frac{n}{P(n)^{K(n)}}) \times (K(n)+1)

。

P(n)

在线性筛时就能顺便求出来，所以考虑求

K(n)

。

若 $P(n) \not = P(\frac{n}{P(n)})$ ，那就是没有多余的最小质因子，此时 $K(n)=1$ 。
若 $P(n) = P(\frac{n}{P(n)})$ ，这样也很简单，只要把指数加一继承一下就行了： $K(n) = K(\frac{n}{P(n)}) +1$ 。

知道这些就够用了。

求解代码：

CPP

d[1]=d[0]=1;
	for(int i=2;i<=n;++i){
		if(!vis[i]){
			prime[++tot]=i;
			P[i]=i,A[i]=1;
			d[i]=2; //素数i的d(i)=2;
		}
		else{
			//不是素数就按照前面的公式求d(i)
			if(P[i]!=P[i/P[i]]) A[i]=1;
			else A[i]=A[i/P[i]]+1;           
			d[i]=(A[i]+1)*d[i/pow(P[i],A[i])];
		}
		for(int j=1;j<=tot&&i*prime[j]<=n;++j){
			vis[i*prime[j]]=1;
			P[i*prime[j]]=prime[j]; //线性筛原理，用最小质因子筛
			if(i%prime[j]==0) break;
		}
	}

3 欧拉函数与欧拉定理

3.1 欧拉函数

欧拉函数

\varphi(n)

表示

1\sim n

中与

n

互质的数的个数，是积性函数。

3.1.1 求单个欧拉函数

假设要求

\varphi(n)

，根据唯一分解定理，

n=\prod p_i^{k_i}

，

p_i

是质数，且

k_i>0

。

那么根据欧拉函数积性性质

\varphi(n)=\prod \varphi( p_i^{k_i} )

，考虑怎么求

\varphi(p^{k})

。

可以发现，如果一个数与

p^k

不互质，那么其一定是

p

的倍数，所以和

p^k

不互质的数的个数是

\frac{p^k}{p} = p^{k-1}

，反过来就得到了

\varphi(p^k)=p^k-p^{k-1} =p^k(1-\frac{1}{p})

。

那么

\begin{aligned} \varphi(n) &= \prod \varphi(p_i^{k_i}) \\ &= \prod p_i^{k_i}(1-\frac{1}{p_i}) \\ &= n \prod (1-\frac{1}{p_i}) \end{aligned}

这样就可以在

O(\sqrt n)

的时间复杂度下求出

\varphi(n)

：

CPP

int tphi(int n) {
	int ans=n;
	for(int i=2;i*i<=n;++i)
		if(n%i==0){
			ans=ans/i*(i-1);    //乘上(1-1/p)
			while(n%i==0) n/=i; //把n中的i全部筛去
		}
	if(n!=1) ans=ans/n*(n-1);   //可能存在一个大于sqrt(n)的质因子
	return ans;
}

3.1.2 线性筛求多个欧拉函数

既然欧拉函数是积性函数，我们就能用线性筛来求

1\sim n

的欧拉函数。

若

i

是素数，那么

\varphi(i)=i-1

。

若

i

是合数，在线性筛中一个合数被筛去当且仅当被其最小质因数筛去，假设

p_1

是

i

的最小质因子，

k_1

是

i

的最小质因子的指数，分类讨论：

$k_1 = 1$ 时，此时 $p_1$ 与 $\frac{i}{p_1}$ 互质，所以 $\varphi(i)=\varphi(\frac{i}{p_1}) \times \varphi(p_1) = \varphi(\frac{i}{p_1}) \times (p_1-1)$ 。
$k_1>1$ 时，此时 $p_1$ 与 $\frac{i}{p_1}$ 不互质， $\frac{i}{p_1}$ 的最小质因数仍然是 $p_1$ ，因为：

\begin{aligned} \varphi(i) &= i \prod(1-\frac{1}{p_i}) \\ \varphi(\frac{i}{p_1}) &= \frac{i}{p_1}\prod(1-\frac{1}{p_i}) \end{aligned}

所以

\varphi(i)= \varphi(\frac{i}{p_1}) \times p_1

。

CPP

void sol(int n){
	phi[1]=1;
	for(int i=2;i<=n;++i){
		if(!phi[i]) phi[i]=i-1,prime[++tot]=i; //i为素数
		for(int j=1;j<=tot&&i*prime[j]<=n;++j){
			if(i%prime[j]==0){                 //i为合数且k1>1
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else                              //i为合数且k1=1
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}

3.1.3 欧拉函数的其他性质

一个最重要的就是：

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

对任意正整数

n

成立。

我们来证明这个，设集合

A=\{1,2,\cdots,n \}

，并将该集合划分成若干个子集

S_d=\{ k \in A \:| \: \gcd(k,n)=d\:\}

，显然任意两个

S

的交集为空，且这些的并集等于

A

，所以

n = |A| = \sum |S_d|

，而且

d|n

，故

n =\sum_{d|n} |S_d|

。

那就考虑怎么求

|S_d|

。

假设

S_d

中一个元素为

k

，有

\gcd(k,n)=d

，设

k=dm

，

m

是正整数，显然

m

能取的数量就是

|S_d|

。所以

k=dm \le n

，

m \le \frac{n}{d}

。又

\gcd(dm,n)=d

，

\gcd(m,\frac{n}{d})=1

。

令

t=\frac{n}{d}

，所以

1\le m\le t

且

\gcd(m,t)=1

，

m

的取到的数量就是

\varphi(t)=\varphi(\frac{n}{d})

，即

|S_d|=\varphi(\frac{n}{d})

。

d|n

，所以

\frac{n}{d}

是整数，且是

n

的一个约数。

现在有了

n=\sum_{d|n} \varphi(\frac{n}{d})

，发现在枚举

d

时，

\frac{n}{d}

都是

n

的正约数且成对，即

d|n

时，

\frac{d}{n}|n

。因为对答案影响只有

\varphi(\frac{n}{d})

，所以上述等式等价于

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

。得证。

~~不要问为什么最后证的这么牵强，这是我自己证的，能大概证出来就已经是我这个菜狗的极限了。~~

3.2 欧拉定理

欧拉定理和扩展欧拉定理常由于解决大指数化简的问题。

设 $a,n \in \mathbb{N}_+$ ，若 $a$ 与 $n$ 互质，则 $a^{\varphi(n)} \equiv 1 \pmod n$ 。

n

为素数时，

\varphi(n)=n-1

，此时欧拉定理变成费马小定理。

那就考虑

n

为其他数，设集合

A

是所有与

n

互质的正整数，即

A=\{ x_1,x_2,\cdots , x_{\varphi(n)} \}

。

令集合

B

为集合

A

中每一个元素乘

a

模

n

构成的集合，即

B=\{ ax_1 \bmod n,ax_2 \bmod n,\cdots , ax_{\varphi(n)} \bmod n\}

，那么

A=B

。

首先证明

B

中的每一个元素都互不相同：

若存在

i \not= j,ax_i \equiv ax_j \pmod n

，那么

a(x_i-x_j)\equiv 0 \pmod n

。因为

a

与

n

互质，

0 < x_i,x_j<n

且

x_i\not= x_j

，故一定不存在一个

(x_i-x_j)

使得

a(x_i-x_j)\equiv 0 \pmod n

成立，得证。

因为

x_i

与

n

互质，

a

也与

n

互质，所以

ax_i

与

n

互质。

A

包括了所有与

n

互质的小于

n

的正整数。所以每一个

0 < ax_i \bmod n <n

都与

A

中的一个元素对应，又

|B|=|A|

且

B

中每个元素互不相同，所以

A=B

。

那么有：

\begin{aligned} \prod_{i=1}^{\varphi(n)} ax_i &\equiv \prod_{i=1}^{\varphi(n)} x_i \pmod n \\ a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} x_i &\equiv \prod_{i=1}^{\varphi(n)} x_i \pmod n \\ a^{\varphi(n)} &\equiv 1 \pmod n \end{aligned}

得证欧拉定理。

3.3 扩展欧拉定理

设 $a,n \in \mathbb{N}_+$ ，有 $a^{2\varphi(n)} \equiv a^{\varphi(n)} \pmod n$ 。

等价地，对于任意的 $a,k,n \in \mathbb{N}_+$ ，若 $k \ge \varphi(n)$ ，那么有 $a^k \equiv a^{k \bmod \varphi(n) + \varphi(n)} \pmod n$ 。

证明：

~~咕咕咕~~。

4 二元线性不定方程

一般来说，形如方程

ax+by=c

，其中

a,b,c

是整数，求整数

x,y

。通常使用裴蜀定理和扩展欧几里得算法来求解。与普通的欧几里得算法（辗转相除法）相似。

4.1 裴蜀定理

若 $a,b$ 不是全为 0 的整数，那么对于任意整数 $x,y$ 满足 $\gcd(a,b) \mid ax+by$ ，且存在整数 $x,y$ ，使得 $ax+by=\gcd(a,b)$ 。

下面是裴蜀定理的证明：

设集合

S

为所有可以表示成

ax+by

的数，即：

S= \{ ax+by,x\in \mathbb{Z},y \in \mathbb{Z}\}

设

d

是集合

S

中的最小正整数（

d=ax_0+by_0

），则有：

$\forall w,w \in S$ ，则有 $d\mid w$ 。

证明：假设

d \nmid w

，则存在

x',y'

使得

d \nmid ax'+by'

。由带余除法的定义可知：

ax'+by'=qd+r

，其中

0 <r<d

。那么有：

\begin{aligned} r&=ax'+by'-qd \\ &=ax'+by'-q(ax_0+by_0) \\ &=a(x'-qx_0)+b(y'-qy_0) \end{aligned}

则

r

是比

d

更小，且在集合

S

中的正整数。故假设不成立，证毕。

当

x=1,y=0

时，

ax+by=a

。

当

x=0,y=1

时，

ax+by=b

。

则有

d\mid a

，

d \mid b

，所以

d

是

a,b

的公约数。

\forall c

，

c

是

a,b

的公约数。

则

c\mid a,c\mid b

，那么有

a=m_1c,b=m_2c

,可以得到:

\begin{aligned} d &= m_1cx_0+m_2cy_0 \\ &= c(m_1x_0+m_2y_0) \end{aligned}

所以

c\mid d

，

d

是

a,b

的最大公约数，得证。

4.2 扩展欧几里得（exgcd）

已知整数 $a,b,c$ ，求二元方程 $ax+by=c$ 的整数解。

4.2.1 求特解

由裴蜀定理可知若

\gcd(a,b) \nmid c

则无解，反之有解。即

\gcd(a,b)

是

c

的倍数。

那么只需要求

ax+by=\gcd(a,b)

的一组解，然后把解同时乘以

\frac{c}{\gcd(a,b)}

即可。

因为

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

。

所以

bx_0+(a \bmod b)y_0= \gcd(b,a \bmod b)

。

如果重复上述操作可以得到：

\begin{aligned} a'x'+0y'&=\gcd(a',0)=a（①） \\ x'=1&,y'=0 \end{aligned}

考虑回代。

假设已经知道了

bx_0+(a \bmod b)y_0=\gcd(b,a \bmod b)

的一组解，如何求

ax+by=\gcd(a,b)

。

因为

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

，所以：

\begin{aligned} ax+by &= bx_0+(a \bmod b)y_0\\ &= bx_0+(a-\left\lfloor\dfrac{a}{b}\right\rfloor b) y_0 \\ &= bx_0+ay_0-\left\lfloor\dfrac{a}{b}\right\rfloor b y_0 \\ &= ay_0+b(x_0-\left\lfloor\dfrac{a}{b}\right\rfloor y_0) \\ \end{aligned}

即：

\begin{cases} x=y_0 \\ y=x_0-\left\lfloor\dfrac{a}{b}\right\rfloor y_0 \end{cases}

这样就可以递归找出特解了。

注意式子

①

，这里的

y'

可不为

0

，

y'

取其它整数虽导致得到的最终结果不同，但是符合题意的一组解，不影响答案。

求解代码：

CPP

void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1; y=0; //y可取其它整数
		return ;
	}
	exgcd(b,a%b,x,y);
	//得到上一组的解
	int tx=x;
	x=y;
	y=tx-a/b*y;
	//得到这一组的解
}

不要忘了最后的解要乘

\frac{c}{\gcd(a,b)}

。

4.2.2 求通解

这个方程显然是有很多个解的，那么如何求所有的解。

现在已经求出了

ax+by=c

的一组解，假设另一个解

ax'+by'=c

。

两式子相减得：

a(x-x')+b(y-y')=0

。

令

\Delta x=x-x',\Delta y=y-y'

，这个方程的的任何一个解与已经求出的特解的差

(\Delta x,\Delta y)

，也一定满足

(a\Delta x+ b \Delta y)=c

。

对于该方程的任意一组解

(x'',y'')

，因为

(ax''+by'')+(a\Delta x+ b \Delta y)=c+0=c

，故

(x''+\Delta x,y''+\Delta y)

也是该方程的一组解。

因此只需求出

a\Delta x+ b \Delta y=0

的所有解即可。

因为对于全部的解

x

的绝对值越大，

y

的绝对值显然越大。

所以令方程

ax+by=0

的一组非零解为

(x_{\min},y_{\min})

，指

x,y

的绝对值最小的一组解。

因为

\left| ax\right|

是

a

的倍数，

|by|

是

b

的倍数，而且

|ax|=|by|

。

所以

|ax|

、

|by|

是

a,b

的公倍数。

要让

|ax|

最小，

|a|

是定值，就是让

|x|

最小，即

a,b

的最小公倍数

\operatorname{lcm}(a, b)=\frac{a\times b}{\gcd(a,b)}

。

因此最小的一组非零解就是

(x_{\min},y_{\min}) = (\frac{b}{\gcd(a,b)},\frac{-a}{\gcd(a,b)})

。

可以证明所有关于

ax+by=0

的解都是

(x_{\min},y_{\min})

的倍数。

令

k \in \mathbb{Z}

，

(x,y)

是得到的特解，那么就得到了通解形式，即

ax+by=c

的所有解：

\large(x+k\frac{b}{\gcd(a,b)} ,y-k\frac{a}{\gcd(a,b)})

5 模意义下的乘法逆元

模意义下的乘法逆元简称“逆元”。

若存在一个整数

x

，使得

ax \equiv 1 \pmod p

，则称

x

为

a

在模

p

意义下的乘法逆元，即为

a^{-1} \pmod p

。

5.1 逆元的求法

5.1.1 扩展欧几里得算法求逆元

ax \equiv 1 \pmod p

可以拆成同余方程

ax + py = 1

，求得的

x

就是

a

在模

p

意义下的乘法逆元。

由裴蜀定理可以发现存在

a

在模

p

意义下的乘法逆元当且仅当

a

与

p

互素。

5.1.2 费马小定理求逆元

利用费马小定理

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

，可以改写等式：

a^{p-1} = a \times a^{p-2} \equiv 1 \pmod p

，显然

a^{p-2}

就是逆元。

但是费马小定理要求

p

是质数且

a

不能是

p

的倍数，前者限制条件在扩展欧几里得里没有要求，所以用扩展欧几里得求逆元比费马小定理求逆元的实用性更广。

5.2 逆元的性质

唯一存在性：

由上文求逆元的方式可知存在

a

在模

p

意义下的乘法逆元只需要满足

a

与

p

互素，且

0 < a^{-1} < p

，这个逆元是唯一确定的。

证明很简单：假设存在

0 < x_1,x_2 <p

，

x_1<x_2

。那么

ax_1 \equiv ax_2 \pmod p

，

a(x_2 - x_1) \equiv 0 \pmod p

。因为

a

与

p

互素，所以

x_2 - x_1

是

p

的倍数，但是

0 < x_2-x_1<p

，不是

p

的倍数。与前提假设矛盾，得证。

值得注意的是，逆元的 “唯一性”是指在模

p

的意义下，如果只是根据定义来解那么是有很多解的，例如

3^{-1}\equiv 5 \pmod 7

，

12

和

19

也可以表示，与

5 \pmod 7

等价。

其他相对来说没那么重要的性质：

运算兼容性：

(a \times b)^{-1} \equiv a^{-1} \times b^{-1} \pmod p

。

互逆性： 若

0 <a,b <p

，

ab \equiv 1 \pmod p

，那么

a

是

b

在模

p

意义下的乘法逆元，

b

也是

a

在模

p

意义下的乘法逆元。

5.3 逆元的作用

在进行模运算时有时会出现求

\frac{a}{b} \bmod p

的情况，根据模运算的运算规律除法是不能直接模运算的，但是利用逆元

b \times b^{-1} \equiv \pmod p

可以化成

\frac{a}{b} \times b \times b^{-1} \equiv a \times b^{-1} \pmod p

这样乘的形式，就可以直接进行模运算了。

而且在处理

ax \equiv b \pmod p

这样的方程时，两边同时乘

a^{-1}

可以化简为

x \equiv b \times a^{-1} \pmod p

。

在计算组合数

C^{n}_{m} = \frac{m!}{n!(m-n)!}

时也可以利用逆元将分母转换为乘法。

5.4 *威尔逊定理

同余式 $(p-1)! \equiv -1 \pmod p$ 成立的充要条件是 $p$ 为素数。

必要性证明（

p

是素数

\Rightarrow

(p-1)! \equiv -1 \pmod p

）：

设集合

A=\{x \:| \: 1 \le x <p,x\in \mathbb{N} \}

。那么

\forall d \in A

，

d

在模

p

意义下的乘法逆元

d^{-1}

显然存在，且根据逆元的唯一性，

d^{-1} \in A

。

由根据逆元的互逆性：

1 \times 2 \times 3 \times \cdots \times (p-1) = 1^{-1} \times 2^{-1} \times \cdots \times (p-1)^{-1} = (p-1)!

因为

p-1 \equiv -1 \pmod p

且

p^{-1} = p

，又

1 = 1^{-1}

，且剩下的元素能两两配对，故：

1 \times 2 \times 2^{-1} \times \cdots \times (p-1) \equiv 1 \times 1 \times \cdots \times -1 \pmod p

即：

(p-1)! \equiv -1 \pmod p

充分性证明（

(p-1)! \equiv -1 \pmod p

\Rightarrow

p

是素数）：

假设

p

是合数，则存在一个整数

1 < d < p

，使得

d \: |\:p

。

显然有：

d \: | \: (p-1)!

，即

(p-1)! \equiv 0 \pmod d

。

由已知条件：

(p-1)! \equiv 1 \pmod p

，由

d

与

p

的关系和上述同余式可以得到：

0 \equiv -1 \pmod d

显然

d = \pm 1

，但是

d>1

，故假设不成立，得证。

6 线性同余方程组

形如：

\begin{cases} x\equiv a_1 & \pmod {m_1} \\ x\equiv a_2 & \pmod {m_2} \\ x\equiv a_3 & \pmod {m_3} \\ &\cdots\\ x\equiv a_n & \pmod {m_n} \end{cases}

的方程称为线性同余方程组，对于模数互质的特殊情况，可以用中国剩余定理（CRT）解决。

对于一般情况就只能使用扩展中国剩余定理（exCRT）解决。

6.1 中国剩余定理（CRT）

CRT 只能用来解决

m_i

两两互质的情况。

令

M= \prod m_i,M_i= \frac{M}{m_i}

。

显然

M_i

与

m_i

互质，则

M_i

在模

m_i

意义下的乘法逆元

M_i^{-1}

存在。

即：

M_i \times M_i^{-1} \equiv 1 \pmod {m_i}

，

a_iM_i M_i^{-1} \equiv a_i \pmod {m_i}

。

对于

j \ne i

，因为

M_j=\prod_{i\ne j} m_i

，则

M_j

是

m_i

的倍数。

所以

a_j M_j M_j^{-1} \equiv 0 \pmod {m_i}

。（注意，这里

M_j^{-1}

是指模

m_j

意义下的逆元，后面的也是。）

令

x= \sum a_i M_i M_i^{-1}

。

\forall i，

有：

\begin{aligned} x &\equiv \sum a_i M_i M_i^{-1} \\ &\equiv a_i M_i M_i^{-1} + \sum_{i \ne j} a_j M_j M_j^{-1} \\ &\equiv a_i + \sum_{i \ne j} \: 0 \\ &\equiv a_i \pmod {m_i} \end{aligned}

x

就是方程的一个解。

对于 $k \in \mathbb{Z}$ ，那么 $x+kM$ 也是该方程的解。

证明：

kM \equiv 0 \pmod {m_i},x + kM \equiv kM+\sum a_i M_i M_i^{-1} \equiv 0+a_i \equiv a_i \pmod {m_i}

。

不存在其他解。

证明：假设存在另一个解

x'

，显然满足

x' \not\equiv x \pmod M

。

但是

x' \equiv a_i \pmod {m_i},x \equiv a_i \pmod {m_i}

。

所以

x' - x \equiv 0 \pmod {m_i}

对所有

i

成立。

因为

m_i

两两互质，所以

\operatorname{lcm}(m_1,m_2,\cdots,m_n) = m_1 \times m_2 \times \dots \times m_n = M

。

故

x'-x \equiv 0 \pmod M

，与前提假设矛盾。得证。

6.2 扩展中国剩余定理（exCRT）

把“

m_i

两两互质的条件”删除时，用 exCRT。

exCRT 本质上与 CRT 完全不同，CRT 的核心思想是利用逆元求解，这里没有了互质的条件，意味着核心思想变了。所以 exCRT 和 CRT 就是完全不同的两种算法，只是解决的问题相似而已。

如果方程组只有一个方程：

x \equiv a \pmod {m}

，那么该方程的最小非负整数解显然为

a

。

如果只有两个方程

\begin{cases} x \equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \end{cases}

，因为一个方程可以直接求出答案，所以考虑把这两个方程合并成一个方程：

把同余式改写成等式：

x=a_1+k_1m_1=a_2+k_2m_2

。

移项：

k_1m_1-k_2m_2=a_2-a_1

。

这刚好是一个二元方程，可以用 exgcd 求解

k_1

。

注意，根据裴蜀定理，若

\gcd(m_1,m_2) \nmid (a_2-a_1)

则无解。

求解出

k_1

后，可以得到一个特解

x'=a_1+k_1m_1

。

现在已经得到了特解，那么

\begin{cases} x \equiv a_1 \pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \end{cases}

的通解为

x'+k \times \operatorname{lcm} (m_1,m_2)

，其中

k\in \mathbb{Z}

。

这很显然，

\operatorname{lcm} (m_1,m_2)

同时是

m_1

和

m_2

的倍数，故

\begin{cases} x + k \times \operatorname{lcm} (m_1,m_2)\equiv a_1 +0\pmod {m_1} \\ x+ k \times \operatorname{lcm} (m_1,m_2)\equiv a_2 +0\pmod {m_2} \end{cases}

。

我们令

x_0

是通解中的最小非负整数，那么原来的两个方程可以合并为：

x \equiv x_0 \pmod {\operatorname{lcm} (m_1,m_2)}

这里的

x_0

显然小于

\operatorname{lcm} (m_1,m_2)

，并且没有其他大于等于零小于

\operatorname{lcm} (m_1,m_2)

的整数解，这里由通解就能直接看出来，不再证明。

合并方程就是 exCRT 的核心操作，如此反复执行合并操作，就可以把原来的

n

个方程合并成一个方程，进而得到解。

洛谷P4777核心代码：

CPP

signed main(){
	int n,a1,b1,a2,b2; scanf("%lld%lld%lld",&n,&a1,&b1);
	for(int i=1;i<n;++i){
		//a1,a2是上一组方程
		scanf("%lld%lld",&a2,&b2);
		int k1,k2;
		int d=exgcd(a1,a2,k1,k2);
		int bg=a2/d; //k1的特解形式
		//判断无解
		if((b2-b1)%d!=0) return !printf("Impossbile\n");
		k1=(mul(k1,(b2-b1)/d,bg));//求出一种解
		//相当于k1=(k1*(b2-b1)/d%bg)，这里用了龟速乘
		
		//更新新的方程
		b1=k1*a1+b1;
		a1=a1*bg;
		b1=(b1%a1+a1)%a1;//求出最小非负的b1
	}
	printf("%lld\n",b1);
}
}

7 组合数学与计数

这一部分可详见我的题解。

7.1 二项式定理

若 $n$ 是正整数，则有： $\begin{aligned} (x+y)^n = \sum_{i=0}^n C_{n}^{i} x^i y^{n-i} \end{aligned}$ 。

用数学归纳法证明：

当

n=1

时原式显然成立。

假设

n=k

时原式成立，则

n=k+1

时，有：

\begin{aligned} (x+y)^{k+1} &= (x+y)(x+y)^k \\ &=(x+y) \sum_{i=0}^{k}C_{k}^{i} x^i y^{k-i} \\ &=(x+y) (C_k^0 y^k+C_k^1 x y^{k-1}+\dots+C_k^{k-1}x^{k-1}y+C_k^k x^k) \\ &=x^{k+1} + y^{k+1} + (C_k^0+C_k^1)xy^k+(C_k^1+C_k^2)x^2y^{k-1}+\dots+(C_k^{k-1}+C_k^k)x^ky \\ &= x^{k+1} + y^{k+1} + \sum_{i=1}^k (C_k^{i-1}+C_k^{i})x^i y^{k-i+1} \end{aligned}

因为

\begin{aligned} C_k^{i-1}+C_k^{i} &= \frac{k!}{(i-1)!(k-i+1)!} +\frac{k!}{i!(k-i)!} \\ &= \frac{k!\:i!\:(k-i)!+k!\:(i-1)!\:(k-i+1)!}{i! \: (i-1)! \: (k-i)! \: (k-i+1)!} \\ &= \frac{(k+1)!}{i! (k-i+1)!} \\ &= C_{k+1}^i \end{aligned}

所以

\begin{aligned} (x+y)^{k+1} &= x^{k+1} + y^{k+1} + \sum_{i=1}^k C_{k+1}^ix^i y^{k-i+1} \\ &=\sum_{i=0}^{k+1}C_{k+1}^ix^i y^{k-i+1} \end{aligned}

因此

n=k+1

时原式也成立，得证。

7.2 卢卡斯定理（Lucas 定理）

一个引理：若

p

是素数，则有：

(x+y)^p \equiv x^p + y^p \pmod p

。

证明：由二项式定理可知：

\begin{aligned} (x+y)^p = \sum_{i=0}^p C_{p}^{i} x^i y^{p-i} \end{aligned}

。

其中当

1 \le i < p

时：

\begin{aligned} C_p^i &= \frac{p!}{i!(p-i)!} \\ &= \frac{p\times(p-1)!}{i \times (i-1)!(p-i)!} \\ &= \frac{p}{i} C_{p-1}^{i-1} \end{aligned}

所以

\begin{aligned} C_p^i & \equiv \frac{p}{i} C_{p-1}^{i-1} \\ & \equiv p \times i^{-1} C_{p-1}^{i-1} \\ & \equiv 0 \pmod p \end{aligned}

其中

i^{-1}

表示

i

在模

p

意义下的乘法逆元。

原式只剩下

i=0,p

两项，得证。

Lucas 定理：

若 $p$ 是素数，则有： $C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p$ 。

证明：

根据带余除法，令

n=ap+b,m=cp+d

，其中

0 \le b,d < p

。

根据二项式定理得到式子一：

(1+x) ^n \equiv \sum_{i=0}^{n} C_n^i x^i \pmod p

根据二项式定理和引理得到式子二：

\begin{aligned} (1+x) ^n &\equiv (1+x)^{ap+b} \\ &\equiv ((1+x)^p)^a\times(1+x)^b\\ &\equiv (1+x^p)^a \times(1+x)^b \\ &\equiv (\sum_{i=0}^a C_a^i x^{ip})(\sum_{j=0}^b C_b^j x^j) \pmod p \end{aligned}

由式子一可知

x^m

的系数为

C_n^m

。

由式子二可知

x^m=x^{cp+d}

的系数为

C_a^c C_b^d

。

因为

\lfloor \frac{n}{p} \rfloor = a ,\lfloor \frac{m}{p} \rfloor = c,n \bmod p =b,m \bmod p=d

。

所以

C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p

，证毕。

在求解时，根据费马小定理：

(m!)^{p-1} \equiv 1 \pmod p,[(n-m)!]^{p-1} \pmod p

。

那么有：

C_n^m=\frac{n!}{m!(n-m)!} \equiv n! \times m!^{p-2} \times (n-m)!^{p-2} \pmod p

这样就可以求解了。

参考资料

大致是按参考程度排列的。

《深入浅出程序设计竞赛（进阶篇）》高等教育出版社，编著：汪楚奇。
同余代数——Alex_Wei。
基础数论笔记——Tomwsc。
OI Wiki-数论。
《数论：概念与问题》哈尔滨工业大学出版社，编著：[美]Titu Andreescu。
扩展中国剩余定理——阮行止。

文章操作

前言

1 数论中的基础知识

1.1 整除

1.1.1 定义

1.1.2 定理

1.1.3 证明

1.2 同余

1.2.1 定义

1.2.2 定理

1.2.3 证明

1.3 数论函数

1.3.1 积性函数

1.3.2 加性函数

1.4 模运算

2 素数

2.1 唯一分解定理

2.2 费马小定理

2.3 素数筛

2.3.1 普通筛

2.3.2 埃氏筛

2.3.3 线性筛

*2.3.4 线性筛求积性函数

3 欧拉函数与欧拉定理

3.1 欧拉函数

3.1.1 求单个欧拉函数

3.1.2 线性筛求多个欧拉函数

3.1.3 欧拉函数的其他性质

3.2 欧拉定理

3.3 扩展欧拉定理

4 二元线性不定方程

4.1 裴蜀定理

4.2 扩展欧几里得（exgcd）

4.2.1 求特解

4.2.2 求通解

5 模意义下的乘法逆元

5.1 逆元的求法

5.1.1 扩展欧几里得算法求逆元

5.1.2 费马小定理求逆元

5.2 逆元的性质

5.3 逆元的作用

5.4 *威尔逊定理

6 线性同余方程组

6.1 中国剩余定理（CRT）

6.2 扩展中国剩余定理（exCRT）

7 组合数学与计数

7.1 二项式定理

7.2 卢卡斯定理（Lucas 定理）

参考资料

相关推荐

评论