斩杀线计算大师

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

设
即可以遍历z使得得到扩展欧几里得版的不定方程
首先对于形式，必须满足倍数才能有解

解

先求出的一组特解
然后令同时乘上,就得到的一组特解
那么，的通解可以表示为

那么只需要求得x和y大于0的时候即可，但是用while去加会tie，那么就采用取模的方式
对于x，因为每次都加上,为了得到一个最小正整数x,最大正整数y，可以令
$$

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;
}