斩杀线计算大师

吐槽一下：牛客的公式渲染不怎么舒服，写出来不好看，我在本地markdown里写latex都很好看的QAQ

设 $\ ax + by + cz = k$
即可以遍历z使得 $ax + by = k - cz$ 得到扩展欧几里得版的不定方程
首先对于 $ax + by = c$ 形式，必须满足 $c是gcd(a,b)$ 倍数才能有解

解

先求出 $ax + by = gcd(a,b)$ 的一组特解 $x_0,y_0$
然后令 $x_0,y_0$ 同时乘上 $\frac{c}{d}$ ,就得到 $ax +by = c$ 的一组特解 $(\frac{c}{d})x_0,(\frac{c}{d})y_0$
那么， $ax + by = c$ 的通解可以表示为
$图片说明$
那么只需要求得x和y大于0的时候即可，但是用while去加会tie，那么就采用取模的方式
对于x，因为每次都加上 $\frac{b}{d}$ ,为了得到一个最小正整数x,最大正整数y，可以令
$ $x = (\frac{c}{d}x_0 \% \frac{b}{d} + \frac{b}{d}) \% \frac{b}{d} , \ \ y =\frac{ (c - a * x)} {b}$ $反之，得到最小正整数y和最大正整数x，可以令$ $x = \frac{(c - b * y)} {a}, \ \ y = (\frac{c}{d}y_0 \% \frac{a}{d} + \frac{a}{d})\%\frac{a}{d}$ $

void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a, x = 1, y = 0;
        return;
    }
    ex_gcd(b, a % b, d, y, x);
    y -= x * (a / b);
}
void solve(ll a, ll b, ll c){
    ll x, y, d;
    ex_gcd(a, b, d, x, y);
    if(c % d != 0)return;//无解
    x = c / d * x, y = c / d * y;
    ll u = b / d;
    x = (x % u + u) % u;
    y = (c - a * x) / b;
}

本题代码

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a, x = 1, y = 0;
        return;
    }
    ex_gcd(b, a % b, d, y, x);
    y -= x * (a / b);
}
int main(){
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    for(ll z = 0; z < k / c; z++){
        ll cc = k - z * c;
        ll x, y, d;
        ex_gcd(a, b, d, x, y);
        if(cc % d != 0)continue;
        x = cc / d * x, y = cc / d * y;
        x = (x % (b / d) + (b / d)) % (b / d);
        y = (cc - x * a) / b;
        if(x >= 0 && y >= 0){
            printf("%lld %lld %lld\n", x, y, z);
            break;
        }
    }
    return 0;
}