数论相关

扩展欧几里得算法

基础

欧几里得算法可以用于求 a,ba,b 的最大公因数:

1
2
3
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}

扩展欧几里得算法可以用于求方程 ax+by=gcd(a,b)ax+by=gcd(a,b) 的一组整数解 x,yx,y

1
2
3
4
5
6
7
8
9
int exgcd(int a,int b,int &x,int &y){
if(!b){
x = 1,y = 0;
return a;
}
int t = exgcd(b,a%b,y,x);
y -= a / b * x;
return t;
}

二元一次方程

求特解

根据翡蜀定理,类似于 ax+by=gcd(a,b)ax+by=gcd(a,b) 的方程必定有整数解。

推广到一般情况: ax+by=cax+by=c 这样的普通二元一次方程方程也可以用exgcd求解。

定义 t=gcd(a,b)t = gcd(a,b) ,如果 ctc|t 则有解,反之无解。

如果有解,定义 k=ctk = \frac{c}{t} ,将 cc 除以 kk 得一个新方程 ax+by=t=gcd(a,b)ax+by=t=gcd(a,b)

这个新方程可以使用exgcd解出一组特解 x0,y0x_0,y_0 。因为新方程由原方程的 cc 除以 kk 得到,所以原方程的特解 {x1=x0×ky1=y0×k\left\{\begin{aligned}x_1&=x_0 \times k\\y_1&=y_0 \times k\end{aligned}\right.

如果你想要的是x的最小正整数解(使 xx 最小),那么你可能需要对 x1,y1x_1,y_1 做一些处理。

{x1=(x1modb+b)modby1=cax1b\left\{\begin{aligned}x_1 &= (x_1 \bmod b + b) \bmod b \\y_1 &= \frac{c-ax_1}{b}\end{aligned}\right.

方便起见,后文的 x1,y1x_1,y_1 都指这里的最小正整数解。

exgcd找到的不一定是最小正整数解(事实上,它甚至有可能不是正整数),但一定是整数解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int exgcd(int a,int b,int &x,int &y){
if(!b){
x = 1,y = 0;
return a;
}
int t = exgcd(b,a%b,y,x);
y -= a / b * x;
return t;
}
inline bool linear_equation(int a,int b,int c,int &x,int &y){//得到二元一次方程 ax+by=c的解
int t = exgcd(a,b,x,y);//直接求出ax+by=gcd(a,b)=t的解,这样只需要跑一遍exgcd,不用先跑一遍gcd验证答案
if(c%t!=0) return false;//无整数解
int k = c / t;
x *= k,y *= k;//得到原方程的解
x = (x % b + b) % b;//得到最小正整数解
y = (c - ax) / b;
return true;//有整数解
}

求通解

手玩一下方程 4x+2y=164x + 2y = 16 ,可以找到以下的正整数解。

i123
x123
y642

发现对于方程 ax+by=cax+by=c ,把 x+=b/gcd(a,b),y-=a/gcd(a,b),便可以得到另一组解。

得到通解公式:

{x=x0+m×bgcd(a,b)y=y0m×agcd(a,b)\left\{ \begin{aligned} x&=x_0+m \times \frac{b}{gcd(a,b)}\\ y&=y_0-m \times \frac{a}{gcd(a,b)} \end{aligned} \right.

mm 为任意整数。

很显然, xx 越大 yy 越小(因为 ax+byax+by 的和恒定)。

这在求 x,yx,y 的最大/最小值时非常有用。

正整数解的数量

得出了通解公式后就可以得出正整数解的数量。显然,当 xx 为最小正整数值时, yy 为最大正整数值。

x1+1bgcd(a,b)my11agcd(a,b)\lfloor \frac{-x1+1}{\frac{b}{gcd(a,b)}} \rfloor \leq m \leq \lfloor \frac{y_1-1}{\frac{a}{gcd(a,b)}} \rfloor

直接算出 mm 的整数值数量即可。

只有正整数解的数量,没有整数解的数量。

二元不定方程整数解是无限多的。

线性同余方程

每一节的相同字母的意义不一定一样!

类似于 axb(modm)ax \equiv b \pmod m 的方程被称为线性同余方程

原方程可以变换为 ax=my+bax = my + baxmy=bax - my = b

然后把 mm 取相反数,就得到 ax+my=bax+my=b

直接使用上一节提到的exgcd解二元一次方程的方法就可以解出了。

别忘了把 yy 取反!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int a,int b,int &x,int &y){
if(!b){
x = 1,y = 0;
return a;
}
int t = exgcd(b,a%b,y,x);
y -= a / b * x;
return t;
}
int congruence_equation(int a,int b,int m){
int x,y,g=exgcd(a,m,x,y);
if(b%g!=0) return -114514;//无解
return (x%m+m)%m;//转为最小正整数解
}

逆元

众所周知,取模运算不影响加法,减法,乘法的结果,但是影响除法的结果。

所以如果题目需要你取模的式子中有除法,就需要使用逆元。

定义

如果 ax1(modm)ax \equiv 1 \pmod m ,则 xx 称为 amodba \bmod b 的逆元,记作 a1a^{-1}

求逆元

求逆元的方法有exgcd法,快速幂(费马小定理)法等。这里主要讲解exgcd法。

求解逆元与求解线性同余方程是同一个原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
int exgcd(int a,int b,int &x,int &y){
if(!b){
x = 1,y = 0;
return a;
}
int t = exgcd(b,a%b,y,x);
y -= a / b * x;
return t;
}
int inv(int a,int m){
int res,qwq,g = exgcd(a,m,res,qwq);
return res;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!