POJ 2142 The balance

POJ 2142 The balance | EXGCD

题目:

求ax+by=c的一组解,使得abs(x)+abs(y)尽量小,满足前面前提下abs(ax)+abs(by)尽量小

题解:

exgcd之后,分别求出让x尽量小和y尽量小的解,取min即可

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int a,b,c,x,y,u1,u2,v1,v2,g;
 6 int exGcd(int a,int b,int &x,int &y)
 7 {
 8     if (b==0) return x=1,y=0,a;
 9     int r=exGcd(b,a%b,y,x);
10     y-=(a/b)*x;
11     return r;
12 }
13 int main()
14 {
15     while (scanf("%d%d%d",&a,&b,&c),a+b+c>0)
16     {
17     g=exGcd(a,b,x,y);
18     a/=g,b/=g,c/=g;
19     u1=(x%b*c%b+b)%b;
20     v1=(c-u1*a)/b;
21     if (v1<0) v1=-v1;
22     v2=(y%a*c%a+a)%a;
23     u2=(c-v2*b)/a;
24     if (u2<0) u2=-u2;
25     if (u1+v1>u2+v2 || (u1+v1==u2+v2 && a*u1+b*v1>a*u2+b*u2))
26         u1=u2,v1=v2;
27     printf("%d %d
",u1,v1);
28     }
29     return 0;
30 }