扩展欧几里得算法

发表于 更新于 分类于

扩展欧几里得算法求解同余方程

1
2
求关于x的同余方程 
ax≡1(modb) 的最小正整数解。

原理：

题目的意思即：(ax-1) mod b = 0 => ax-1=by,y为整数 => ax-by=1存在整数解

我们小学二年级就学过有个东西叫做裴蜀定理，这个定理说：若a,b为整数，gcd(a,b)为a,b的最大公约数，那么ax+by一定是gcd(a,b)的整数倍。简单来说，ax+by=m(a,b,m∈Z) 存在整数解 <=> gcd(a,b)|m，即m能被gcd(a,b)整除

并且有解时会有无数个解，怎么求呢？

这里我们用m=gcd(a,b)时来举例子：设d=gcd(a,b)，ax+by=d

由辗转相除法我们知道：d=gcd(a,b)=gcd(b,a%b)，d也是b和a%b的最大公约数，因此也满足：bx+(a%b)y=d，设q=int(a/b)，则a%b=a-qb，那么bx+(a-qb)y=d ==> ay+b(x-qy)

我们得到了迭代公式，若对方程bx+(a%b)y=d可求得一个整数解(x2,y2)，a×y2+b(x2-q×y2)，则（y2，x2-q×y2）方程ax+by=1的一个解，

x1=y2，y1=x2-a/b*y2

其中a/b是取int

这样的话我们就可以一直辗转相除（具体见辗转相除的博客）直到b=0时，a恰好为gcd(a,d)，那么这个时候ax + 0y = d，所以此时x=1，不妨取y=0作为一组解，即一个特解x=1，y=0。然后进而用递归求出原始的ax+by=d的解（a,b前后不一样的喔），但是这个时候得到的也只是其中一个特解x0,y0，通解为x′=x0+K∗b/d；y′=y−K∗b/d(K为任意整数)，至于证明这里就不过多赘述了

现在还剩一个问题，怎么找到最小正整数解x，

1
( x % b + b ) % b

欧克，所有问题解决，回到代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y,y=t-a/b*y;
	return d;
}
int main(){
	int a, b, x, y;
	cin >> a >> b;
	exgcd(a,b,x,y);
	x=(x%b+b)%b;
	cout << x << '\n';
	return 0;
}