欧几里得算法

欧几里得算法是用来求最大公约数的,gcd(a,b)=gcd(b, a%b),如此递归下去,直到a%b==0,然后返回。

最终,gcd(a,b)=gcd(c,0),其中,a,b的最大公约数就是c

扩展欧几里得算法(exgcd)

扩展欧几里得算法是解决诸如:求整数x和y使得ax+by=gcd(a,b)的问题的。

这里借用oi-wiki中的证明

然后,代码如下:

int Exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    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;
}

转载请注明来源:https://www.longjin666.top/?p=1171

你也可能喜欢

发表评论