exgcd(拓展欧几里得)

碎碎念

回家过中秋还不如待在寝室emm......

甚至在家吹感冒了QwQ，带着重感冒回校参加第一次晚自习

浅浅证了一下之前欠下的线性逆元和exgcd

exgcd

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;
}

因为gcd没学会，所以本文只讲如何从gcd拓展到exgcd

首先我们要求a*x1+b*y1=gcd(a,b)的一组解

假设我们已经有了b*x2+(a%b)*y2=gcd(b,a%b)的一组解(x2,y2)

将第一个式子变化即得(a%b+a/b*b)*x1+b*y1=gcd(a,b)

再整理即得x1*(a%b)+((a/b)*x1+y1)*b=gcd(a,b)

容易得出一组等式x1=y2，(a/b)*x1+y1=x2

整理后就可以得到由(x2,y2)得到(x1,y1)的式子

x1=y2,y1=x2-(a/b)*y2

而gcd到最后时有方程gcd(a,b)*x+0*y=gcd(a,b)

显然(1,0)是其一组解，依次向前推即可