一，题意： 有两个类型的砝码,质量分别为a,b;现在要求称出质量为d的物品, 要用多少a砝码(x)和多少b砝码(y)，使得(x+y)最小。（注意：砝码位置有左右之分）。 二，思路： 1，砝码有左右位置之分，应对比两种情况 i，a左b右，得出方程 ax1 - by1 = d ; ii，b左a右，得出方程 bx2 - ay2 = d 。 2，利用扩展欧几里德算法，解出(x1,y1)、(x2,y2)，并求出最小x1和x2，以及相对应的y1,y2。 3，输出x1+y1和x2+y2 中的最小值。 三，步骤： 1，由题意得出两个方程 i，ax1 - by1 = d ; ii，bx2 - ay2 = d 。 2，代入算法，解出两个方程的解(x1,y1)、(x2,y2)，并求出最小x1和x2，以及相对应的y1,y2. x 为最小正整数时候的解 x = (x % a + a) % a 和y为最小整数时候的解 然后比较即可 (详细步骤请参照本博客poj1061或者poj2115)。 3， 判断步骤 i，x1+y1最小时，输出x1，y1 ii，x2+y2最小时，输出y2，x2。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int Extend_gcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } else { int r=Extend_gcd(b,a%b,y,x); y-=x*(a/b); return r; } } int main() { int a,b,n; while(cin>>a>>b>>n) { if(a+b+n==0) break; int x,y; int gcd=Extend_gcd(a,b,x,y); int vx=x*(n/gcd); int t=b/gcd; vx=(vx%t+t)%t; int vy=(n-a*vx)/b; if(vy<0) vy=-vy; y=(y*n/gcd); t=a/gcd; y=(y%t+t)%t; 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 ); } }