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成立。
它的一个重要推论是：a,b 互质的充要条件是存在 整数x,y使ax+by=1.转载于:https://www.cnblogs.com/DukeLv/p/8406940.html
相关资源：数据结构—成绩单生成器