/*刚拿此题时一头雾水，当看完一次同余方程时方才有点头绪.....后来在又在求最值问题上遇到麻烦。最后才在数学推导下才AC此题.....第一次深刻体会到数学对解题的重要性....下面说一下我的解题思路.....
1.首先通过Gcd函数求出n1,n2的最大公约数g以及满足条件的x,y: n1*x+n2*y=n;（递归运用:x0=1,y0=0;x=y1,y=(x1-n1/n2*y1)）
显然当n不能被g整除时显然没解....这里有一个问题：Gcd函数求出的x,y为什么刚好能使得|x|+|y|最小？？请求数学达人指导
2.求出满足条件的m1,m2使得m1*n1+m2*n2=n (1)：由1得,x*n1+y*n2=g (2)....结合（1（2）:m1=n*x/g+t*n2/g,m2=n*y/g-t*n1/g;这里的t是一个参数，但仍能满足（1）式。
3.由m1>=0,m2>=0可得他t1=<t<=t2;（注意t的取值必须为整数）
4.由c=c1*m1+c2*m==》c=num1+t*(c1*n2-c2*n1)....因此c的大小取决于c1*n2-c2*n1的正负以及t的值....之后的过程在代码中很明了了。
1 #include<iostream>
2 #include<math.h>
3 using namespace std;
4 long Gcd(long p,long q,long *x,long *y)
5 {
6 long x1,y1;
7 long g;
8 if(q>p)
9 return (Gcd(q,p,y,x));
10 if(q==0)
11 {
12 *x=1;
13 *y=0;
14 return p;
15 }
16 g=Gcd(q,p%q,&x1,&y1);
17 *x=y1;
18 *y=(x1-p/q*y1);
19 return g;
20 }
21 int main()
22 {
23
24 long n,c1,c2,n1,n2,x,y,gcd,t1,t2,t,a,b;
25 //freopen("c:\\in.txt","r",stdin);
26 // freopen("c:\\8522.out","w",stdout);
27 while(cin>>n)
28 {
29 if(n==0)
30 break;
31 cin>>c1>>n1>>c2>>n2;
32 gcd=Gcd(n1,n2,&x,&y);
33 t1=ceil(-n*(double)x/(double)n2);
34 t2=floor(n*(double)y/(double)n1);
35 if((t1>t2)||(n%gcd!=0))
36 {
37 cout<<"failed\n";
38 continue;
39 }
40 if(c1*n2>=c2*n1)
41 t=t1;
42
43 else
44 t=t2;
45 a=n*x/gcd+t*n2/gcd;
46 b=n*y/gcd-t*n1/gcd;
47 cout<<a<<" "<<b<<endl;
48 }
49 return 0;
50 }