欧几里得算法&&扩展欧几里得算法

欧几里得算法：gcd(a,b)=gcd(b,a%b);证明略
扩展欧几里得算法：y-=a/b*x;
应用判断不定方程是否有整数解，求不定方程的整数解，判断在规定范围内有多少整数解.
[cpp]
#include<iostream> 
#include<string.h> 
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.zzzyk.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

补充：软件开发 , C++ ,