題意：有兩種類型的砝碼，每種的砝碼質量a和b給你，現在要求稱出質量為d的物品，要求a的數量x和b的數量y最小，以及x+y的值最小。www.2cto.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
