歐幾裡得算法：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.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
