题意：用x个a毫克的砝码与y个b毫克的砝码恰好称得质量为d毫克的阿斯匹林，求使x+y最小的x和y。
题目链接：http://poj.org/problem?id=2142
——>>好题。因为欧几里德扩展算法只能求ax + by = gcd(a, b)；所以，先求a, b的最大公约数gcd_ab，对于ax + by = d，令a, b, d同除以gcd_ab，然后可求得(a/gcd_ab)x + (b/gcd_ab)y = 1的最小整数解，然后将求得的这组解乘以d/gcd_ab得x0, y0，就是ax + by = d一组解，由数论知识得ax + by = d的所有解为： x = x0 - bt, y = y0 + at（t为参数），那么，要使|x|+|y|最小，可令x = 0求得一组解，再令y = 0求得一组解，两组比较取较小者就好。
#include <cstdio>using namespace std;typedef long long LL;LL gcd(LL a, LL b)
{return b == 0 ? a : gcd(b, a%b);
}
void Euler_extends(LL a, LL b, LL& x, LL& y)
{if(!b){x = 1;y = 0;}else{Euler_extends(b, a%b, y, x); //白书加强版的写法，个人觉得，妙极！y -= a / b * x;}
}
int main()
{LL a, b, d, x, y;while(~scanf("%I64d%I64d%I64d", &a, &b, &d)){if(!a && !b && !d) return 0;LL gcd_ab = gcd(a, b);a /= gcd_ab;b /= gcd_ab;d /= gcd_ab;Euler_extends(a, b, x, y);LL y1 = (y * d % a + a) % a;LL x1 = (d - b * y1) / a;if(x1 < 0) x1 = -x1;LL x2 = (x * d % b + b) % b;LL y2 = (d - a * x2) / b;if(y2 < 0) y2 = -y2;if(x1+y1 < x2+y2) printf("%I64d %I64d\n", x1, y1);else printf("%I64d %I64d\n", x2, y2);}return 0;
}