扩展欧几里得算法

对于任意整数a，b，存在一对整数x，y，满足ax+by=gcd(a,b)。
证明：
当b=0时显然x=1，y=0是一组解。
若b>0，则,假设存在一对整数满足x，y满足


令就得到了


对欧几里得算法的递归过程应用数学归纳法，显然成立。
假设我们通过上述递归过程求解出x,y为，这是一组特解。对ax+by=gcd(a,b)来说，,是通解。
对于更一般的形式他有解当且仅当。先求出的解然后将扩大倍就可以了。
通解可以表示为：,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;
}