满足d=gcd(a,b)=ax+by
gcd(b,a%b)=bx'+(a%b)y'=bx'+(a-(a/b)b)y'=bx'+ay'-b(a/b)y'=ay'+b(x'-(a/b)y')
只需满足
x=y'
y=x'-(a/b)y'
//d=gcd(a,b)=ax+by
#include<iostream>
using namespace std;
int extEuclid(int a,int b,int&x,int&y)
{
int d,tmp;
if(!b){x=1;y=0;return a;}
d=extEuclid(b,a%b,x,y);
tmp=x;
x=y;
y=tmp-(a/b)*y;
return d;
}
int main(){
int a,b,x=0,y=0;
cin>>a>>b;//99 78
cout<<extEuclid(a,b,x,y)<<'\t'<<x<<'\t'<<y;
//system("pause");
return 0;
}
奇怪的是VC6.0编译通过后执行，无论如何x和y的值始终为0。而用dev－c++编译通过后显示结果正常！
如果将输出改为
cout<<extEuclid(a,b,x,y)<<endl;
cout<<'\t'<<x<<'\t'<<y;
VC6.0编译后运行也就显示正常了！
I DON'T KNOW WHY?