POJ 2142 The Balance 扩展欧几里得
题意：有两种类型的砝码，每种的砝码质量a和b给你，现在要求称出质量为d的物品，要求a的数量x和b的数量y最小，以及x+y的值最小。
思路：是扩展欧几里得的应用。设ax + by = 1,求出x和y的值，因为我们要求ax + by = n的解，所以需要将x y的值乘以n。因为题目中要求x和y的值都要为正，然而，易知，ax + by = 1在a和b都为正数的情况下，x 和 y必有一个数是负的。因此我们需要把x 和 y的值转化为合法的正值。我们先把x转化为正值，易知，把x转化为正值的方式是 x = (x % a + a) % a，这样x就成为最小的正值，我们再根据所求出的x的最小正值求出y的值，则 y = (n – a * x) / b，若求出的y为负值，则把y变正，意思就是砝码放置的位置有左右之分，可以左面的减去右面的，也可以右面的减去左面的。同理，再求出y为最小合法正值时x的解，将这两种情况比较取小的即可。
代码：
#include <iostream>#include <cstdio>#include <string.h>using namespace std;int gcd(int a,int b){if(b == 0)return a;return gcd(b,a%b);}void extend_Eulid(int a,int b,int &x,int &y){if(b == 0){ x = 1; y = 0; return;}extend_Eulid(b,a%b,x,y);int temp = x;x = y;y = temp - a / b * y;}int main(){freopen("1.txt","r",stdin);int a,b,n;while(scanf("%d%d%d",&a,&b,&n)){ if(a + b + n == 0) break; int x,y; int gcdab = gcd(a,b); a /= gcdab; b /= gcdab; n /= gcdab; extend_Eulid(a,b,x,y); int vx = x * n; vx = (vx %b + b) % b; int vy = (n - a * vx) / b; if(vy < 0) vy = -vy; y = y * n; y = (y % a + a) % a; x = (n - b * y) / a; if(x < 0) x = -x; if(x + y > vx + vy){ x = vx; y = vy; } printf("%d %d\n",x,y);}return 0;}