题解 CF1244C 【The Football Season】

2019-10-14 19:12:32


观察题面可得可以用exgcd做,但是Pretest 5/7会爆long long...

然后我喜闻乐见地用Py3水了一发,但是由于系数没有化简 $\color{red}{FST}$ 了......

import sys
x = 0
y = 0
def exgcd(a,b):
    global x,y
    if b == 0:
        x = 1
        y = 0
        return a
    ret = exgcd(b,a % b)
    t = x
    x = y
    y = t - (a // b) * y
    return ret

n,p,w,d = map(int,input().split())
ret = exgcd(w,d)
if p % ret: #方程无解情况
    print(-1)
else:
    x *= p // ret 
    y *= p // ret
    d //= ret #系数化简......
    w //= ret
    # print(x,y)
    if x < 0:
        tmp = (-x + d - 1) // d #x加上/减去化简后的d,y减去/加上化简后的w,方程仍然成立
        x += tmp * d
        y -= tmp * w
    elif y < 0:
        tmp = (-y + w - 1) // w
        x -= tmp * d
        y += tmp * w
    if x >= 0 and y >= 0:
        if w > d: #这是比赛时的代码改的,当时没有仔细读题
            tmp = y // w
            y %= w
            x += tmp * d
        else:
            tmp = x // d
            x %= d
            y += tmp * w
    if x + y > n or x < 0 or y < 0:
        print(-1)
    else:
        print(x,y,n - x - y)