程序员算法

扩展欧几里得算法

2020-08-04  本文已影响0人  dachengquan

扩展欧几里得算法

对于任意整数a,b,存在一对整数x,y,满足ax+by=gcd(a,b)。
证明:
当b=0时显然x=1,y=0是一组解。
若b>0,则gcd(a,b)=gcd(b,a\pmod b),假设存在一对整数满足x,y满足b*x+(a\mod b)*y= gcd(b,a\mod b)
b*x + (a-b*\lfloor a/b \rfloor)y =gcd(b,a\mod b)
ay+b(x-\lfloor a/b \rfloor y)=gcd(b,a\mod b)
x' = y,y' = (x-\lfloor a/b \rfloor y)就得到了
a*x'+b*y' = gcd(b,a\mod b)
a*x'+b*y' = gcd(a,b)
对欧几里得算法的递归过程应用数学归纳法,显然成立。
假设我们通过上述递归过程求解出x,y为x_0,y_0,这是一组特解。对ax+by=gcd(a,b)来说,x = x_0+k*\frac b {gcd(a,b)},y = y_0-k*\frac a {gcd(a,b)}是通解。
对于更一般的形式ax+by=c,d = gcd(a,b)他有解当且仅当d\mid c。先求出ax+by=d的解x_0,y_0然后将x_0,y_0扩大\frac c d倍就可以了。
通解可以表示为:x = \frac c d x_0+k*\frac b {d},y = \frac c d y_0-k*\frac a {d}k取整数。

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,y,x);
  y-=a/b*x;
  return d;
}
上一篇下一篇

猜你喜欢

热点阅读