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ǎ崽 閱讀(221)
評論(0) 編輯 收藏 引用