G题、The Balance(拓展欧几里得算法)
题目大意：给出 a , b , c 求ax + by = c，且使得a+b最小

难点：如何求$ax + by = c$的通解

拓展欧几里得算法可以用来求解形如 $ax + by = c$ 的线性方程的通解。

首先，使用欧几里得算法求出 $a$ 和 $b$ 的最大公约数 $d$，同时求出 $d$ 的一个解 $(x_0, y_0)$，使得 $ax_0 + by_0 = d$。

接着，如果 $c$ 能被 $d$ 整除，即 $c \mod d = 0$，那么方程 $ax + by = c$ 有解。否则，方程无解。

如果方程有解，我们可以通过 $(x_0, y_0)$ 得到方程的一个特解 $(x_1, y_1)$，其中 $x_1 = x_0 \times (c/d)$，$y_1 = y_0 \times (c/d)$。

那么，方程 $ax + by = c$ 的通解为 $(x, y) = (x_1 + k \times (b/d), y_1 - k \times (a/d))$，其中 $k$ 为任意整数。

这个通解的推导可以通过以下步骤来理解：

我们已经有一个特解 $(x_1, y_1)$，使得 $ax_1 + by_1 = c$。我们希望找到方程的所有解。

设 $(x, y)$ 是方程 $ax + by = c$ 的另一个解。我们可以将 $(x, y)$ 表示为特解 $(x_1, y_1)$ 加上一个新的解 $(x’, y’)$，即 $(x, y) = (x_1 + x’, y_1 + y’)$。

将 $(x, y)$ 代入方程 $ax + by = c$ 中得到：
$$a(x_1 + x’) + b(y_1 + y’) = c$$
展开后得到：
$$ax_1 + by_1 + ax’ + by’ = c$$
由于 $ax_1 + by_1 = c$，所以上式可以简化为：
$$ax’ + by’ = 0$$

这意味着 $(x’, y’)$ 是方程 $ax + by = 0$ 的解。

我们要找到$x’$和$y’$的最小取值,则$x’ = b/d ,y’ = -a/d$是所需的最小解

因此，$(x’, y’)$ 可以表示为 $(x’, y’) = (k \times (b/d), -k \times (a/d))$，其中 $k$ 是任意整数。

将 $(x’, y’)$ 代入 $(x, y) = (x_1 + x’, y_1 + y’)$ 中，得到通解：
$$(x, y) = (x_1 + k \times (b/d), y_1 - k \times (a/d))$$

这就是为什么通解是 $(x, y) = (x_1 + k \times (b/d), y_1 - k \times (a/d))$，其中 $k$ 是任意整数。

本题求|x| + |y| 的最小的情况，

可得
$$|x| + |y| = |x_1 + k\times(b/d)| +|y_1 - k\times(a/d)|$$
我们使用三分算法求得这个最小值就可以了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, d;
ll x, y;
ll X, Y;
ll exgcd(ll a,ll b,ll &x,ll &y){//扩展欧几里得算法
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll gcd = exgcd(b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - a / b * y;
    return gcd;
}
int main(){
    while(cin >> a >> b >> d){
        if(a == 0 && b == 0 && d == 0)
            return 0;
        ll gcd = exgcd(a, b, x, y);
        a /= gcd, b /= gcd;
        x = x * d / gcd;
        y = y * d / gcd;
        //通解为x + k * (b / gcd)   y - k * (a / gcd),找出最小的k
        int l = -1e5, r = 1e5;
        while(l <= r){
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;//三分点
            int x1 = abs(x + b * mid1), y1 = abs(y - a * mid1);
            int x2 = abs(x + b * mid2), y2 = abs(y - a * mid2);
            if(x1 + y1 > x2 + y2) {
                l = mid1 + 1;
                X = x1, Y = y1;
            }
            else{
                r = mid2 - 1;
                X = x2, Y = y2;
            }
        }
        cout << X << " " << Y << endl;
    }
    return 0;
}