擴展歐幾里德算法即可。
以下是我的代碼：
#include<stdio.h>
void expand_gcd(long a,long b,long &d,long &x,long &y)
{
if(b==0){d=a;x=1;y=0;}
else{expand_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
long a,b,d,x,y;
while(scanf("%ld%ld",&a,&b)==2)
{
expand_gcd(a,b,d,x,y);
printf("%ld %ld %ld\n",x,y,d);
}
return 0;
}
posted on 2010-03-28 14:58
lee1r 閱讀(833)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)學(xué)/數(shù)論