欧几里得算法&&扩展欧几里得算法 - c++编程基础

欧几里得算法：gcd(a,b)=gcd(b,a%b);证明略
扩展欧几里得算法：y-=a/b*x;
应用判断不定方程是否有整数解，求不定方程的整数解，判断在规定范围内有多少整数解.
[cpp]
#include?
#include?
using namespace std;?
int a,b,x,y,d;?
/*void gcd(int a,int b )
{
??? if(!b){x=1;y=0;d=a;}
??? else?
??? {
??????? gcd(b,a%b);
??????? int temp=x;
??????? x=y;
??????? y=temp-a/b*x;
?
??? }
}*/?

void gcd(int a,int b,int &d,int &x,int &y)?
{?
??? if(!b) x=1,y=0,d=a;?
??? else gcd(b,a%b,d,y,x),y-=a/b*x;?
?????
}?
int main()?
{??? www.2cto.com
??? int T;?
??? scanf("%d",&T);?
??? while(T--)?
??? {?
??????? int a,b;?
??????? scanf("%d%d",&a,&b);?
??????? gcd(a,b,d,x,y);?
??????? printf("%d*%d+%d*%d=%d\n",a,x,b,y,d);?
??? }return 0;?
?
}?
作者：smallacmer