首先说到wmdty算法，当然是为了求出两个数的最大公约数
当然，使用的结论是gcd(a，b )=gcd (b，a mod b ) ) ab且r=a mod b，r可以不是0 ) )。
但是，为什么a和b的最大公约数和b和a mod b的最大公约数相同呢？
也就是说，证明a mod b具有与a和d相同的最大公约数
若将a和b的最大公约数设为r，则a一定可以表示为a=k*b r，换句话说，如果a mod b的所得为0，则a一定是b的倍数。
由于r可以被a和b整除，且r=a-k*b，所以如果等式的两边同时除以gcd(a，b )=d，则得到r/d=a/d-k*b/d，r也一定可以被d整除，因此得到证书
码面：求最大公约数时，a mod b一定为0，所以a mod b==0时成为程序的终点，此时，b成为最大公约数()
因此，可以根据该特性写入具有递归性质gcd函数
# include bits/stdc.husingnamespacestd； int n，a，b； intgcd(intx，int y ) if ) x%y==0) return y； //三目运算符可以在一行中完成，这样写可以更清楚地返回gcd (y，x % y )； (}int main ) ) { cin n； //n组数据while(n----) { cin a b； coutgcd(a，b ) endl； } return 0； }或algorithm的__gcd ) )函数，也可以直接求出两者的最大公约数
——33543——3——3————3——33——3——33——333————33——33——33——33——3——33——33——33——33——3——3——33——33——333——333——333
扩展wmdty算法比朴素的wmdty算法具有更多的功能
但是，要解释这个功能，就必须引入裴勇俊定理
(后蜀定理)对于任意整数a，b和它们的最大公约数d，对于未知数x和y，满足ax by=m，有解，且只有当m为d的倍数时，有解，解就有无限个。 摘自——百度百科
正好，扩展wmdty算法新增加的功能是求出满足a=b，b=a mod b的解的组，可以从这个组求出所有的解
如果d=gcd(x，y )，则显然gcd (y，xmod y )=d
此外，由于通过存在a、b，ax by=d成立，并且通过存在a1、b1，a1y1B1(xmody )成立，所以联合后可以求出x1=y、y1=x1-a/b*x
所以得到代码
# includeiostreamusingnamespacestd； int n； intexgcd(inta，int b，int x，int y ) ) if (！ //1 { x=1，y=0； return a； (intd=EXgcd ) b、a % b、y、x )； //2y-=(a/b ) ) x； 返回d； (}int main ) ) { cin n； while(n-- ) { int a、b、x、y； cin a b； exgcd(a，b，x，y )； cout x ' ' y ' ' endl； } return 0； }是一处递归结束后开始执行2后的部分，此时需要修正的只有y1，如果需要得到最大公约数则返回d，如果不需要参照修正x则为y即可
得到x0和y0组的解后，得到一般解的公式。 x=x0 k*b1，y=y0-k*a1，其中b1=b/d，a1=a/d