扩展欧几里得算法的实现

1. 扩展欧几里得
   用于求解方程 ax+by=gcd(a,b)ax+by=gcd(a,b) 的解

当 b=0b=0 时 ax+by=aax+by=a 故而 x=1,y=0x=1,y=0
当 b≠0b≠0 时

因为
gcd(a,b)=gcd(b,a%b)
gcd(a,b)=gcd(b,a%b)
而
bx′+(a%b)y′=gcd(b,a%b)
bx′+(a%b)y′=gcd(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
故而

x=y′,y=x′−⌊a/b⌋∗y′
x=y′,y=x′−⌊a/b⌋∗y′
因此可以采取递归算法 先求出下一层的x′x′和y′y′ 再利用上述公式回代即可

2. 对于求解更一般的方程 ax+by=cax+by=c
   设 d=gcd(a,b)d=gcd(a,b) 则其有解当且仅当 d|cd|c
   求解方法如下:

用扩展欧几里得求出 ax0+by0=dax0+by0=d 的解

则a(x0∗c/d)+b(y0∗c/d)=ca(x0∗c/d)+b(y0∗c/d)=c
故而特解为 x′=x0∗c/d,y′=y0∗c/dx′=x0∗c/d,y′=y0∗c/d
而通解 = 特解 + 齐次解

而齐次解即为方程 ax+by=0ax+by=0的解

故而通解为 x=x′+k∗b/d,y=y′−k∗a/dk∈zx=x′+k∗b/d,y=y′−k∗a/dk∈z
若令 t=b/dt=b/d, 则对于 xx 的最小非负整数解为 (x′%t+t)%t(x′%t+t)%t
3.应用: 求解一次同余方程 ax≡b(modm)ax≡b(modm)
则等价于求

ax=m∗(−y)+b
ax=m∗(−y)+b
ax+my=b
ax+my=b

有解条件为 gcd(a,m)|bgcd(a,m)|b,然后用扩展欧几里得求解即可

特别的 当 b=1b=1 且 aa与mm互质时 则所求的xx即为aa的逆元

C++ 代码
#include
using namespace std;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
if(b==0){
x = 1, y = 0;
return a;
}
int x1,y1,gcd;
gcd = exgcd(b, a%b, x1, y1);
x = y1, y = x1 - a/b*y1;
return gcd;
}
int main(){
int n,a,b,x,y;
cin>>n;
while(n–){
cin>>a>>b;
exgcd(a,b,x,y);
cout< }
return 0;
}

一.拓展欧几里得算法 O(n∗log(a+b))O(n∗log(a+b))
1.1拓展欧几里得算法解决的问题:对于任意给定的两个正整数a,b,求解x,y使得ax+by=(a,b) //(a,b)的意思为,a和b的最大公约数

1.2问题的引入:裴蜀定理
给定任意一对正整数a,b,存在非零整数x,y,使得ax+by=(a,b)

1.3x与y的求解
由欧几里得算法拓展由欧几里得算法拓展
设 d = gcd(a,b)
方式一:
exgcd(a,b,x,y)=exgcd(b,a%b,y,x)exgcd(b,a%b,y,x)⇒b×y+(a−[ab]×b)×x=d⇒b×(y−[ab]×x)+a×x=d∴y更新为y−[ab]×xexgcd(a,b,x,y)=exgcd(b,a%b,y,x)exgcd(b,a%b,y,x)⇒b×y+(a−[ab]×b)×x=d⇒b×(y−[ab]×x)+a×x=d∴y更新为y−[ab]×x
方式二:
exgcd(a,b,x,y)=exgcd(b,a%b,x,y)exgcd(b,a%b,x,y)⇒b×x+(a−[ab]×b)×y=d⇒p×(x−[ab]×y)+a×y∴y更新为x−[ab]×y,x更新为yexgcd(a,b,x,y)=exgcd(b,a%b,x,y)exgcd(b,a%b,x,y)⇒b×x+(a−[ab]×b)×y=d⇒p×(x−[ab]×y)+a×y∴y更新为x−[ab]×y,x更新为y
二.代码
方式一代码 O(n∗log(a+b))O(n∗log(a+b))

#include

using namespace std;

void exgcd(int a,int b,int& x,int& y)
{
if(!b)
{
x=1,y=0;
return ;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
while(n–)
{
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout< }
return 0;
}
方式二代码 O(n∗log(a+b))O(n∗log(a+b))

#include
using namespace std;
void exgcd(int a,int b,int& x,int& y)
{
if(!b)
{
x=1,y=0;
return ;
}
exgcd(b,a%b,x,y);
int t = y;
y = x-a/b*y;
x = t;
}
int main()
{

int n;
scanf("%d",&n);
while(n--)
{
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    exgcd(a,b,x,y);
    printf("%d %d\n",x,y);
}
return 0;
1
2
3
4
5
6
7
8
9
10

}