题目链接：
?id=2142
题目大意：
有一个天平，还有质量为a和质量为b的砝码，砝码的数量不限且天平左右两端均可放砝码，现在要求
在天平上惩处质量为c的物品。那么问题来了：怎样放置砝码，才能使放置的砝码数量尽可能的少；当
砝码数量相同时，总质量尽可能的少。
思路：
假设放置x个质量为a的砝码和y个质量为b的砝码，题目就变为了求解a*x + b*y = c的其中一组解，使
得|x| + |y|尽可能小，若相等，则a|x| + b|y|尽可能小。设d = gcd(a，b)，首先用扩展欧几里得算法出
a/d*x + b/d*y = c/d的一组一组解(x0，y0)，那么通解就可以表示为x = x0 + b/d *t，y = y0 – a/d *t。
|y0 – a/d*t|先单
调递减再单调递增。设a > b，则斜率 a/d > b/d，那么|x| + |y| = |x0 + b/d*t| + |y0 – a/d*t| 总的函
数在 t < y0*d/a 的时候单调递减，在 t >= y0*d/a的时候单调递增。那么|x| + |y|在 t = y0*d/a取得最
小值因为x、y都为整数，t也是整数，所以最小值就在t的上下范围内取整，然后比较两者大小即可得到
结果。
还有一种方法，虽然照做了。。。但是还是不理解。希望大神帮忙解答。
x为正数，，则y为0或负数，若果x为0为负数，则y为正数。先求
出 |x| 的最小值x1为 (x0%b + b) % b，得出|y|的值y1 = |(c/d – a/d*x0)/(b/d)|。同理，也可求出 |y|的最
小值y2为(y0%a + a) % a，再得出|x|的值x2 = |(c/d – b/d*y0)/(a/d)|。比较x1+y1和x2+y2的值，较小
的就是|x| + |y|最小结果。不清楚为什么这样可以AC。参考博文：
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define LL __int64using namespace std;LL GCD(LL a,LL b){if(b == 0)return a;return GCD(b,a%b);}void ExGCD(LL a,LL b,LL &d,LL &x,LL &y){if(!b){x = 1;y = 0;d = a;}else{ExGCD(b,a%b,d,y,x);y -= x*(a/b);}}int main(){LL a,b,c,temp,d;while(cin >> a >> b >> c && (a||b||c)){LL x0,y0;LL gcd = GCD(a,b);a /= gcd;b /= gcd;c /= gcd;ExGCD(a,b,d,x0,y0);LL x,y,x1,y1,x2,y2;x1 = x0*c;x1 = (x1%b + b)%b;y1 = (c – a*x1)/b;if(y1 < 0)y1 = -y1;y2 = y0*c;y2 = (y2%a + a)%a;x2 = (c – b*y2)/a;if(x2 < 0)x2 = -x2;if(x1+y1 < x2+y2)x = x1,y = y1;elsex = x2,y = y2;cout << x << ' ' << y << endl;}return 0;}
愚者用肉体监视心灵，智者用心灵监视肉体
