前言

感谢x某q的帮助

这是它的博客（只有找本人才会解释的博客）：

---

正题

题目链接：

---

大意

有三种东西，重量不同，A种只能放左边；B种只能放右边；C种只有一个，两边都可以放。A和B随便放多少个都行但是C必须放，要求两边重量相等。求在满足放的东西最少，之后满足重量最小的放置方案

---

解题思路

首先推出公式

Ax=By+cAx=By+c

oror

By=Ax+cBy=Ax+c

然后移项得

Ax−By=cAx−By=c

oror

By−Ax=cBy−Ax=c

然后是不是又有些眼熟，没错了就是扩欧ax+by=cax+by=c。之后我们发现我们之前那个(x∗((b−a)/d)%(k/d)+(k/d))%(k/d)(x∗((b−a)/d)%(k/d)+(k/d))%(k/d)的公式如果既求x又求y的话就会不成立。

然后就场外求助用一种方法，用最小的x来求y和用最小的y来求x之后可以判断那个更优。

---

代码

#include
    
     #include
     
      using namespace std;int x,y,a,b,c,x1,y1,x2,y2;int gcd(int a,int b){    if (b==0)    {        x=1;        y=0;        return a;    }    int d=gcd(b,a%b),k=x;    x=y;    y=k-(a/b)*y;    return d;}int main(){    while (true)    {        scanf("%d%d%d",&a,&b,&c);        if (a==0&&b==0&&c==0) return 0;        int gcde=__gcd(a,b);        a/=gcde;b/=gcde;c/=gcde;//提前除去方便些        int d=gcd(a,b),g=b;        x1=(x*c%b+b)%b;//求最小的x        y1=(a*x1-c)/b;//算出y        if (y1<0) y1=-y1;//确定是那个公式        y2=(y*c%a+a)%a;//求最小y        x2=(b*y2-c)/a;//算出x        if (x2<0) x2=-x2;//确定公式        if (x1+y1