http://acm.hdu.edu.cn/showproblem.php?pid=2669
//欧几里德算法(Euclid)
#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y)//辗转相除法求最大公约数GCD
  {
if(b == 0)
 {
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return r;
}
int main()
  {
int m,n,a,b,r;
while(scanf("%d%d",&a,&b)+1)
 {
r=exgcd(a,b,m,n);
if(r==1)//最大公约数为1时
 {
while(m<0)
 {
m+=b;
n-=a;
}
printf("%d %d\n",m,n);
}
else printf("sorry\n");
}
return 0;
}
|