来源：

大致题意：给你n个球，给你两种盒子。第一种盒子每个盒子c1美元，可以恰好装n1个球；第二种盒子每个盒子c2元，可以恰好装n2个球。找出一种方法把这n个球装进盒子，每个盒子都装满，并且花费最少的钱。

假设第一种盒子买n1个，第二种盒子买n2个，则c1*n1+ c2*n2= n。由扩展欧几里得 ax+by= gcd(a,b)= g ,(a=n1,b=n2),如果n%g!=0，则方程无解。

ax+by=gcd(a,b)= g两边同时乘以n/g, 可以解出m1=nx/g, m2=ny/g,所以通解为m1=nx/g + bk/g, m2=ny/g - ak/g, 又因为m1和m2不能是负数，所以m1>=0, m2>=0,所以k的范围是     -nx/b <= k <= ny/a，且k必须是整数。

所以

k1=ceil(-nx/b)

k2=floor(ny/b)

如果k1>k2的话则k就没有一个可行的解，于是也是无解的情况。

想要花费的最少，也就相当于放一颗弹珠所花费的最少。即

                   c1/n1<?>c2/n2

                   c1*n2<?>c2*n1

如果c1*n2<c2*n1, 即第一种的盒子要更多。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;ll exgcd(ll a, ll b, ll&x, ll&y){    if (b == 0)    {        x = 1;        y = 0;        return a;    }    ll r = exgcd(b, a%b, y, x);    ll t = x;    y = y - a/b*t;    return r;}int main(){    //freopen("in.txt","r",stdin);    ll n;    ll c1,n1,c2,n2;    while(scanf("%lld",&n),n)    {        scanf("%lld%lld%lld%lld",&c1,&n1,&c2,&n2);        ll x,y,a1,a2;        ll g=exgcd(n1,n2,x,y);        //printf("%lld\n%lld %lld\n",g,x,y);        if(n%g!=0)        {            printf("failed\n");            continue;        }        ll k1=ceil(-n*x*1.0/n2);        ll k2=floor(n*y*1.0/n1);        if(k1>k2)        {            printf("failed\n");            continue;        }        if(c1*n2