扩展欧几里得算法1.ax+by=gcd(a,b)
扩展欧几里得算法来解决这样一个问题：给定两个非零整数a和b，求一组整数解(x,y),使得ax+by=gcd(a,b)成立，其中gcd(a,b)表示a和b的最大公约数。
gcd(a,b)-->gcd(b,a%b)-->.....--->gcd(a,0)最终返回a的值，所以就有一组解成立，a*1+b*0=gcd。此时有x=1,y=0
利用上面的式子反推最原始的x和y。
当计算gcd(a,b),有ax1+by1=gcd成立；下一步计算gcd(b,a%b)时，有bx2+(a%b)y2=gcd成立。
因此ax1+by1=bx2+(a%b)y2成立，化简后
x1=y2
y1=x2-(a/b)y2
因此就有啦如下代码：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 { if(b==0) { x=1;y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=x; x=y; //把x y变成上一层的 y=temp-(a/b)*y; return r; //得到a b的最大公因数 }