題意吧：一個家伙有一種天平，這種天平只有兩種重量的砝碼a和b，現在要稱出重量為c的物品，問你至少需要多少a和b，答案需要滿足a的數量加上b的數量和最小，並且他們的重量和也要最小。（兩個盤都可以放砝碼）
分析：
這題我剛剛開始還以為是動規或者搜索，也算是碰了一鼻子的灰吧。
假設a砝碼我們用了x個，b砝碼我們用了y個。那麼天平平衡時，就應該滿足ax+by==c。x,y為正時表示放在和c物品的另一邊，為負時表示放在c物品的同一邊。
於是題意就變成了求|x|+|y|的最小值了。x和y是不定式ax+by==c的解。
剛剛上面已經提到了關於x,y的所以解的同式，即
x=x0+b/d*t
y=y0-a/d*t
你是不是下意識的想要窮舉所有解，取|x|+|y|最小的？顯然是行不通的，仔細分析：|x|+|y|==|x0+b/d*t|+|y0-a/d*t|，我們規定a>b(如果a<b，我們便交換a b)，從這個式子中，我們可以輕易的發現：|x0+b/d*t|是單調遞增的，|y0-a/d*t|是單調遞減的，而由於我們規定了a>b，那麼減的斜率邊要大於增的斜率，於是整個函數減少的要比增加的快，但是由於絕對值的符號的作用，最終函數還是遞增的。也就是說，函數是凹的，先減小，再增大。那麼什麼時候最小呢？很顯然是y0-a/d*t==0的時候，於是我們的最小值|x|+|y|也一定是在t=y0*d/a附近了，我是在t點左右5個點的范圍內取最小的(據說左右一個點都可以，不過我試了一下wa了)。一般這樣的題目就多枚舉幾個點以防萬一嘛！！！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <sstream>
using namespace std;
typedef long long LL;
const int N=10010;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
int ext_gcd(int a,int b,int &x,int &y)
{
int t,ret;
if(!b)
{
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
int gcd(int m,int n)
{
int t;
while(n)
{ t=m%n; m=n; n=t; }
return m;
}
int main()
{
int i,j,a,b,c;
while(scanf("%d%d%d",&a,&b,&c)&&(a+b+c))
{
int f=0;//標記ab交換
if(a<b)
f=1,swap(a,b);
int x,y,t,d;
d=ext_gcd(a,b,x,y);
x=x*c/d; y=y*c/d;
t=y*d/a;
int x1,y1,Min=INF,xx,yy;
for(i=t-5;i<t+5;i++)//掃描周圍5個點
{
x1=abs(x+b/d*i);
y1=abs(y-a/d*i);
if(x1+y1<Min)
{
Min=x1+y1;
xx=x1;yy=y1;
}
}
if(f)
printf("%d %d\n",yy,xx);
else
printf("%d %d\n",xx,yy);
}
return 0;
}
/*
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <sstream>
using namespace std;
typedef long long LL;
const int N=10010;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
int ext_gcd(int a,int b,int &x,int &y)
{
int t,ret;
if(!b)
{
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
int gcd(int m,int n)
{
int t;
while(n)
{ t=m%n; m=n; n=t; }
return m;
}
int main()
{
int i,j,a,b,c;
while(scanf("%d%d%d",&a,&b,&c)&&(a+b+c))
{
int f=0;//標記ab交換
if(a<b)
f=1,swap(a,b);
int x,y,t,d;
d=ext_gcd(a,b,x,y);
x=x*c/d; y=y*c/d;
t=y*d/a;
int x1,y1,Min=INF,xx,yy;
for(i=t-5;i<t+5;i++)//掃描周圍5個點
{
x1=abs(x+b/d*i);
y1=abs(y-a/d*i);
if(x1+y1<Min)
{
Min=x1+y1;
xx=x1;yy=y1;
}
}
if(f)
printf("%d %d\n",yy,xx);
else
printf("%d %d\n",xx,yy);
}
return 0;
}
/*
*/
