牛客练习赛60 - D

题意：

给定 a, b，c，k，求 x，y，z，使得：ax + by + cz = k，且 x >= 0，y >= 0，z >= 0

分析：

扩展欧几里得只能求二元一次方程，自然想到枚举 z 来求 x，y；看到 k 的范围有点大，如果 k = 2*p，c = 2，p 为一个大质数，肯定是跑不过的，考虑枚举 ax + by 的值，设 ax + by = k0，当 k0 = gcd(a,b)d 时 x，y 才会有解，那就有 gcd(a,b)d + cz = k，直接扩欧求出 d 即可，然后在用扩欧求解 ax + by = k0 即可，需要注意的是：cz >= 0，所以 gcd(a,b)d <= k，当 d 取最小非负整数解一定会满足这个条件，同样 x 取最小非负整数解时一定会满足 ax <= k0 吗？为了满足 ax <= k0，k0 就越大越好，也就是 d 越大越好；而扩欧求解后有通解：d' = d + tc/gcd(a,b,c)，t 为整数，再结合 gcd(a,b)d <= k，就能得到 d 的最大取值了

代码：

#include <bits/stdc++.h>

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 2e3+23;
LL ex_gcd(LL a,LL b,LL &x,LL &y){
    if(b == 0){x = 1; y = 0; return a;}
    LL gcd = ex_gcd(b,a%b,x,y);
    LL t = x; x = y; y = t-a/b*y;
    return gcd;
}
LL solve(LL a,LL b,LL &x,LL &y,LL k){   //求解 ax+by = k 的最小非负整数 x
    LL gcd = ex_gcd(a,b,x,y);
    x = k/gcd*x; 
    LL mod = b/gcd;
    x = (x % mod + mod) % mod;
    y = (k-a*x)/b;
    return gcd;
}
int main(){
    LL a,b,c,k,x,y,z; 
    cin >> a >> b >> c >> k;
    LL g = __gcd(a,b);
    LL gcd = solve(g,c,x,y,k);
    LL d = x, mod = c/gcd;
    LL t = (k-d*g)/(mod*g);
    d += mod*t;                   //满足条件的最大的d
    z = (k-d*g)/c;
    LL k0 = d*g;
    solve(a,b,x,y,k0);
    cout << x << " " << y << " "<< z << '\n';
    return 0;
}