【模板】【数论】扩展欧几里得算法

数论

扩展欧几里得算法应用很广：

（1）求解不定方程:

（2）求解模线性方程（线性同余方程）

（3）求解模的逆元

先考虑（1）

对于不定方程 ax+by=c仅当c|gcd(a,b)时方程有解

则可以先求出 ax+by=gcd 的解

因为这不定方程解有无数个，所以我们可以先解出一个通解x0,y0，在利用这个通解表示所有解

因为 ax0+by0=gcd

所以 a(x0+b/gcd*t)+b(y0-a/gcd*t)=gcd

所以x=x0+b/gcd*t, y=y0-a/gcd*t （t为循环变量）

此处t为循环变量，之所以用b/gcd和a/gcd是因为要令通解尽可能多，因保证系数越小

那么如何解出通解呢

先利用欧几里得算法求出最大公约数，

此时 a0=gcd，b0=0

因为 ax+by=0 所以 x=1，y=0（其实y可以为任意数）

那么返回上一层 a0=b1，b0=a1%b1

所以

1
2
3
4
5
gcd=a1x1+b1y1
   =a0x0+b0y0
   =b1x0+(a1%b1)y0
   =b1x0+(a1-a1/b1*b1)y0
   =a1y0+b1(x0-a1/b1*y0)

所以 x1=y0, y1=x0-a1/b1*y0

除此之外还可以根据通解判断一定范围内解的个数（显然）

题目传送门：CodeVS1213

以下基础代码

1
2
3
4
5
6
7
8
9
10
11
12
int gcd(LL a,LL b,LL &x,LL &y){
	if (b==0){
		x=1;
		y=0;
		return a;
	}
	LL k=gcd(b,a%b,x,y);
	LL t=x;
	x=y;
	y=t-a/b*y;
	return k;
}

（2） 关于 ax=b(mod n)

可化为 ax+ny=b

再按如上方法

（3） 所谓逆元，ax=1(mod n)

则可以化为 ax+ny=1

再按如上方法