题目大意：
就是将两种砝码左右摆放，能够在物品放置在天平上时保持平衡
很容易得到 ax + by = t的模线性方程
按题目要求，希望首先满足 |x| + |y| 最小 , 如果有多种情况，再满足所有砝码质量最小，也就是a|x| + b|y|最小
x = x0 + b/g * k
y = y0 - a/g * k
这里可以通过画一个2维坐标图进行观察 x , y 对于k的直线，我假定 b > a ，初始如果 a>b就交换两者数据，记得最后答案交换回来
因为a，b为砝码重量都大于0
所以x是递增直线，y是递减直线
因为假设b > a了，所以x的上升趋势必然大于y的下降趋势
所以只有在x = 0的左右两个点是满足最小的情况的 ， 用xx[2] , yy[2]记录这两个点，然后进行比较即可
/*
当然不交换a ， b 也可以, 那就得在 a > b 的条件下多保存两组数据，此时是在y = 0 的左右两个点
*/
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 int ex_gcd(int a , int &x , int b , int &y) 7 { 8 if(b == 0){ 9 x = 1 , y = 0; 10 return a; 11 } 12 int ans = ex_gcd(b , x , a%b , y); 13 int t = x; 14 x = y , y = t - a/b*y; 15 return ans; 16 } 17 18 void my_swap(int &a , int &b) 19 { 20 int t = a; 21 a = b , b = t; 22 } 23 24 int my_abs(int a) 25 { 26 return a>=0?a:-a; 27 } 28 29 int main() 30 { 31 // freopen("a.in" , "r" , stdin); 32 int a , b , w; 33 while(scanf("%d%d%d" , &a , &b , &w) , a){ 34 int x , y; 35 bool flag = false; 36 if(b < a){ 37 my_swap(a , b); 38 flag = true; 39 } 40 41 int g = ex_gcd(a , x , b , y); 42 int k = w/g; 43 x = k*x , y = k*y; 44 a /= g , b /= g; 45 int xx[2] , yy[2]; 46 if(x >= 0){ 47 xx[0] = x - x/b*b; 48 xx[1] = xx[0] - b; 49 yy[0] = y + x/b*a; 50 yy[1] = yy[0] + a; 51 }else{ 52 xx[0] = x - x/b*b+b; 53 xx[1] = xx[0] - b; 54 yy[0] = y + x/b*a - a; 55 yy[1] = yy[0] + a; 56 } 57 int ansx , ansy; 58 if(my_abs(xx[0]) + my_abs(yy[0]) == my_abs(xx[1]) + my_abs(yy[1])){ 59 if(my_abs(xx[0])*a + my_abs(yy[0])*b < my_abs(xx[1])*a + my_abs(yy[1])*b) 60 ansx = my_abs(xx[0]) , ansy = my_abs(yy[0]); 61 else 62 ansx = my_abs(xx[1]) , ansy = my_abs(yy[1]); 63 } 64 else{ 65 if(my_abs(xx[0]) + my_abs(yy[0]) < my_abs(xx[1]) + my_abs(yy[1])) 66 ansx = my_abs(xx[0]) , ansy = my_abs(yy[0]); 67 else 68 ansx = my_abs(xx[1]) , ansy = my_abs(yy[1]); 69 } 70 if(flag) 71 my_swap(ansx , ansy); 72 printf("%d %d " , ansx , ansy); 73 } 74 return 0; 75 }