POJ 2142 The Balance 扩展欧几里得

题意：有两种类型的砝码，每种的砝码质量a和b给你，现在要求称出质量为d的物品，要求a的数量x和b的数量y最小，以及x+y的值最小。www.zzzyk.com
思路：是扩展欧几里得的应用。设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的解，将这两种情况比较取小的即可。
代码：
[cpp] 
#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; 
} 
作者：wmn_wmn

补充：软件开发 , C++ ,