扩展欧几里德算法即可。
以下是我的代码：
#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 阅读(824)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：数学/数论