欧几里得算法
欧几里得算法是用来求最大公约数的，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中的证明：
然后，代码如下：
代码语言：javascript复制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
