题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1031

题目大意：有n块大理石，然后有两种盒子，cost分别为c1,c2，容量分别为n1,n2，问你装完这些大理石所需要的最小花费是多少

思路分析：设最终选择x个第一种盒子，y个第二种盒子

根据题目，有 n1*x+n2*y=n ，让求T=c1*x+c2*y的最小值

解不定方程，容易想到使用exgcd ,n1*x0+n2*y0=gcd(n1,n2)

比较两式即可得到x=n*x0/gcd(n1,n2),y=n*y0/gcd(n1,n2)

结果肯定为正整数么，若n%gcd（n1,n2)!=0,则无解

通解为 x=n*x0/gcd(n1,n2) +k*n2/gcd(a,b)

         y=n*y0/gcd(n1,n2)-k*n1/gcd(a,b)

同时要求x>=0,y>=0，我们就可以解得k的范围

k1=ceil(-n*x0/n2)<=k<=floor(n*y0/n1)=k2

若k1>k2，说明也是无解

否则带入T表达式 T=c1*(n*x0/gcd(n1,n2) +k*n2/gcd(a,b))+c2*( n*y0/gcd(n1,n2)-k*n1/gcd(a,b))

整理发现这是一个关于k的一次函数，系数为m=c1*n2-c2*n1，若m>=0，递增，取k1

否则取k2

代码：

#include 
     
      #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 d=exgcd(b,a%b,y,x);    y-=a/b*x;    return d;}int main(){    ll n;    ll c1,n1,c2,n2;    while(scanf("%lld",&n)&&n)    {        ll x,y;        scanf("%lld%lld",&c1,&n1);        scanf("%lld%lld",&c2,&n2);        ll g=exgcd(n1,n2,x,y);        if(n%g) {printf("failed\n");continue;}        ll x0=x,y0=y;        x=x*n/g;        y=y*n/g;        ll k1=ceil((-n*x0/(double)n2));        ll k2=floor(n*y0/(double)n1);        if(k1>k2) {printf("failed\n");continue;}        ll t=c1*n2-c2*n1;        ll ans1,ans2;        if(t>=0)        {            ans1=x+k1*n2/g,ans2=y-k1*n1/g;        }        else  ans1=x+k2*n2/g,ans2=y-k2*n1/g;        printf("%lld %lld\n",ans1,ans2);    }}