Poj 2142 The Balance(拡張ユークリッドアルゴリズム)
1331 ワード
題意:2種類の分銅があり、それぞれの分銅の品質aとbは、現在、品質dと呼ばれるものが要求されており、天秤の両側に分銅を置くことができ、aの数量xとbの数量yが最小であり、x+yの値が最小であることが要求されている.
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int a,b,c,x,y;
int exgcd(int a,int b)
{
int t,d;
if(b==0)
{
x=1;
y=0;
return a;
}
d=exgcd(b,a%b);
t=x;
x=y;
y=t-(a/b)*y;
return d;
}
int main()
{
int sum1,sum2,ans1,ans2;
int a1,b1,c1;
while(scanf("%d%d%d",&a,&b,&c),a||b||c)
{
int d=exgcd(a,b);
a1=a/d;
b1=b/d;
c1=c/d;
x=x*c/d;
y=y*c/d;
sum1=abs(x)+abs(y);
sum2=abs(x)*a+abs(y)*b;
ans1=abs(x);
ans2=abs(y);
for(int i=-50000; i<=50000; i++) // x1=x+b/d*t; y1=y-a/d*t;
{
int s1=abs(x+i*b1)+abs(y-i*a1);
int s2=abs(x+i*b1)*a+abs(y-i*a1)*b;
if(s1<sum1||s1==sum1&&s2<sum2)
{
sum1=s1;
sum2=s2;
ans1=abs(x+i*b1);
ans2=abs(y-i*a1);
}
}
printf("%d %d
",ans1,ans2);
}
return 0;
}