扩展欧几里得（E

题目链接：https://cn.vjudge.net/contest/276376#problem/E

题目大意：给你n，m，k，n，m代表当前由于无限个质量为n，m的砝码。然后当前有一个秤，你可以通过秤的左边和右边的砝码种类和数目，能够测出m的质量，然后问你使用两个砝码总和最少的情况。

具体思路:和前面几个题的思路一样，列出等式Ax+By=C,然后再通过扩展欧几里得去解这个式子，当前一共有两组解，一个是通过x，解出y。另一个是通过y，解出x。我们就取这两种的总和最小的情况就可以了。注意x和y都应该是非负数，所以当第一种情况解出的y是负值的时候，y应该取反，第二种情况类似。

AC代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<cmath>
 4 #include<queue>
 5 #include<stdio.h>
 6 #include<algorithm>
 7 using namespace std;
 8 # define ll long long
 9 # define inf 0x3f3f3f3f
10 const int maxn = 1e5+100;
11 ll xo,yo;
12 ll exgcd(ll a,ll b)
13 {
14     if(b==0)
15     {
16         xo=1;
17         yo=0;
18         return a;
19     }
20     ll gcd=exgcd(b,a%b);
21     ll tmp=yo;
22     yo=xo-a/b*yo;
23     xo=tmp;
24     return gcd;
25 }
26 int main()
27 {
28     ll a,b,c;
29     while(~scanf("%lld %lld %lld",&a,&b,&c)&&(a+b+c))
30     {
31         ll t=exgcd(a,b);
32         ll t1=b/t;
33         if(t1<0)
34             t1-=t1;
35         ll x1=(c*xo/t%t1+t1)%t1;
36         ll y1=(c-a*x1)/b;
37         if(y1<0)y1=-y1;
38         ll minn=x1+y1;
39         t1=a/t;
40         ll y2=(yo*c/t%t1+t1)%t1;
41         ll x2=(c-b*y2)/a;
42         if(x2<0)x2=-x2;
43         if(minn>x2+y2)x1=x2,y1=y2;
44       printf("%lld %lld
",x1,y1);
45     }
46     return 0;
47 }