UVA 10090 Marbles 擴展歐幾裡得，10090marbles

UVA 10090 Marbles 擴展歐幾裡得，10090marbles

來源：http://www.cnblogs.com/zxhl/p/5106678.html

大致題意：給你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 <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
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<c2*n1)
        {
            a1=n*x/g+n2*k2/g;
            a2=n*y/g-n1*k2/g;
        }
        else
        {
            a1=n*x/g+n2*k1/g;
            a2=n*y/g-n1*k1/g;
        }
        printf("%lld %lld\n",a1,a2);
    }
    return 0;
}