题解 CF1244C 【The Football Season】

AutumnKite · 2019-10-15 08:19:03 · 题解

其实就是要求 ax+by=c 的一组 x+y 最小的非负整数解。同时又保证了 a>b，那么显然只要使得 y 最小即可。

一开始写了一个扩欧，发现 x,y 同时乘 c/gcd(a,b) 会爆 long long。

回过头来看数据范围，a,b 只有 10^5。我们知道，如果原方程有非负整数解，那么 y 在 [0,a) 中一定存在一个非负整数解。

直接枚举即可。

时间复杂度 O(a)。

#include <cstdio>
long long n, p, a, b, x, y;
int main(){
    scanf("%lld%lld%lld%lld", &n, &p, &a, &b);
    while (y < a && (p - 1ll * b * y) % a) ++y;
    if (y == a) return puts("-1"), 0;
    x = (p - 1ll * b * y) / a;
    if (x < 0 || x + y > n) return puts("-1"), 0;
    printf("%lld %lld %lld\n", x, y, n - x - y);
}