gcd就是求a和b最大公约数，一般方法就是递推。不多说，上代码。
一.迭代法
int gcd(int m, int n) { while(m>0) { int c = n % m; n = m; m = c; } return n; }
二.递归法
int Gcd(int a, int b) { if(b == 0) return a; return Gcd(b, a % b); }
但exgcd是个什么玩意？？？
百度了一下，百科这么讲的：
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然
存在整数对 x，y ，使得 gcd（a，b）=ax+by。
好像很好理解的样子，百度还给了个代码
int gcd(int a,int b,int &x,int &y){ if (b==0){ x=1,y=0; return a; } int q=gcd(b,a%b,y,x); y-=a/b*x; return q; }
？？？什么玩意？？？
于是我又找了一段证明：
证明：
当 b=0 时，gcd(a,b)=a，此时 x=1 , y=0
当 b!=0 时，
设 ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2
又因 a%b=a-a/b*b
则 ax1+by1=bx2+(a-a/b*b)y2
ax1+by1=bx2+ay2-a/b*by2
ax1+by1=ay2+bx2-b*a/b*y2
ax1+by1=ay2+b(x2-a/b*y2)
解得 x1=y2 , y1=x2-a/b*y2
因为当 b=0 时存在 x , y 为最后一组解
而每一组的解可根据后一组得到
所以第一组的解 x , y 必然存在
得证
于是刚才那段代码返回的是a和b的gcd
void exgcd(int a,int b) { if (b) { exgcd(b,a%b); int k=x; x=y; y=k-a/b*y; //k就是上一组的x-- y1 = x2 - a/b*y2; } else y=(x=1)-1; }
还有一个斐蜀定理。。。
若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。