题解 CF1244C 【The Football Season】

灵茶山艾府 · 2019-10-14 15:05:19 · 题解

暴力可过，补一个扩展欧几里得的解法。

记 g=gcd(a,b)，则不定方程 ax+by=g 有无穷组整数解，记其中一个解为 (x_0,y_0)。

对于 ax+by=p，若有 g|p，则解为 (x_0*\frac{p}{g},y_0*\frac{p}{g})，否则无解。

根据线性方程定理，不定方程 ax+by=g 的所有解可表示为 (x_0+k*\frac{b}{g},y_0-k*\frac{a}{g}), k\in Z。

设 a>b，若不定方程有非负整数解 (x,y)，则 y 越小 x+y 也越小。

Python 代码如下：

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    gcd, y, x = exgcd(b, a % b)
    y -= a // b * x
    return gcd, x, y

n, p, a, b = map(int, input().split())

gcd, x, y = exgcd(a, b)
if p % gcd != 0:
    print(-1)
    exit()
p //= gcd
a0 = a // gcd
b0 = b // gcd
x *= p
y *= p

min_y = (y % a0 + a0) % a0
x -= (min_y - y) // a0 * b0
y = min_y
if x < 0:
    print(-1)
    exit()
if x + y > n:
    print(-1)
    exit()
print(x, y, n - x - y)