CF1244C 题解

思路

我们看到题目，给定四个数 \(n\)、\(p\)、\(w\)、\(d\)，求解三元一次不定方程组： \[ \left\{ \begin{array}{l} x\cdot w+y\cdot d=p\\ x+y+z=n \end{array} \right. \] 观察一下你就会发现 \(z\) 的值是你可以随便指定的，因为他只对 \(n\) 产生影响，而不对方程一产生任何贡献。于是我们忽略 \(z\) 的取值。

由此我们就可以把方程组化简为一条二元一次不定方程： \[ x\cdot w+y\cdot d=p \] 由于 \(w>d\)，可以发现使 \(y\) 最小就可以得到一组可能存在的解。因此考虑枚举 \(y\)。分析数据范围可以发现 \(\frac{p}{n}\) 的范围刚好就是 \(w\) 和 \(d\) 的最大范围，因此我们可以证明，如果原方程组有非负正整数解，那么解中的 \(y\) 必定在区间 \([0,\,w)\) 中。

故枚举 \(y \in [0, \,w)\) 然后判断解是否合法即可，若找不到，则原方程必定无解。

代码

#include <iostream>

#define int long long

using namespace std;

int n, p, w, d;

signed main() {
    cin >> n >> p >> w >> d;
    for (int y = 0; y < w; y++) {
        if ((p - y * d) >= 0 && (p - y * d) % w == 0 && n - ((p - y * d) / w + y) >= 0) {
            int x = (p - y * d) / w;
            cout << x << " " << y << " " << n - (x + y);
            return 0;
        }
    }
    cout << -1;
}