http://acm.hdu.edu.cn/showproblem.php?pid=2669
#include<stdio.h>
int x,y;
int exgcd(int a,int b)
{
if(b==0)
{
x = 1;
y = 0;
return a;
}
int g = exgcd(b,a%b);
int t = x;
x = y;
y = t-a/b*y;
return g;
}
int main()
{
int a,b,g;
while(scanf("%d%d",&a,&b)==2)
{
g = exgcd(a,b);
if(g-1)
{
puts("sorry");
continue;
}
if(x>0)
{
y += x/b*a;
x %= b;
printf("%d %d\n",x,y);
}
else
{
y -= ((-x)/b+1)*a;
x = x%b + b;
printf("%d %d\n",x,y);
}
}
return 0;
}
3.8女生专场出先这道数论题目。
一点想法都没有，唉
后来知道是gcd
查了一下资料
知道了上边那过exgcd函数。。
可以求出ax+by=gcd(a,b)
再根据
a*(x+n*b) + b*(y-n*a) = ax+by
算出最小的x
posted on 2009-03-09 20:07
shǎ崽 阅读(217)
评论(0) 编辑 收藏 引用