本文为博主原创文章，欢迎转载，请注明出处 www.cnblogs.com/yangyaojia
The Balance
题目大意
你有一个天平（天平左右两边都可以放砝码）与重量为a,b(1<=a,b<=10000)的两种砝码。让你求出一种方案称出重为c(1<=c<=50000)的物品，如有多种方案，请输出两种砝码需要数量的总和最小的方案。
输入
有若干行，每行三个数，a,b,c。
结束时用0 0 0表示。
输出
若干行，每行两个数，表示每个询问中a的数量与b的数量
如果无解输出 no solution
分析
题目就是求方程 ax+by=c,求出一组解很容易，就用扩展欧几里德求，可是要求出使|x|+|y|最小的解就得想一想。如果是枚举，肯定超时。
有没有什么好的方法求出我们要的x,y? 我们假设a>b ，x0，y0为求得的解，x,y为目标解。
根据扩欧的性质，我们知道
x=x0 + b/gcd*t
y=y0 — a/gcd*t
我们可以得到这样的函数 |x|+|y|=|x0 + b/gcd*t|+|y0 — a/gcd*t| 因为我们知道a>b,所以x0加得比y0减得比慢。因此y0占主导地位，
故当y0 — a/gcd*t=0时|x|+|y|最小。我们可以枚举t±5的解，寻找最小就行。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstring>
#include <climits>
#define MAXN 10000+10
using namespace std;
int e_gcd(int a,int b,int& x,int& y)
{
if(!b)
{
x=;
y=;
return a;
}
int ans=e_gcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
int a,b,c,x,y,gcd,t,minn=~(<<),ansx=,ansy=;
int main()
{
while(scanf("%d%d%d",&a,&b,&c)&&!(a==&&b==&&c==))
{
int flag=;
if(a<b)
{
flag=;
swap(a,b);
}
gcd=e_gcd(a,b,x,y);
minn=~(<<),ansx=,ansy=;
if(c%gcd) {printf("no solution\n");continue;}
x*=(c/gcd);y*=(c/gcd);
t=(y*gcd)/a;
for(int i=t-;i<=t+;i++)
{
if(abs(x+b/gcd*i)+abs(y-a/gcd*i)<minn)
{
minn=abs(x+b/gcd*i)+abs(y-a/gcd*i);
ansx=abs(x+b/gcd*i),ansy=abs(y-a/gcd*i);
}
}
if(flag==) printf("%d %d\n",ansx,ansy);
else printf("%d %d\n",ansy,ansx);
}
return ;
}