题解 CF1244C 【The Football Season】

SIGSEGV

2019-10-14 19:12:32

Solution

观察题面可得可以用exgcd做,但是Pretest 5/7会爆long long... 然后我喜闻乐见地用Py3水了一发,但是由于系数没有化简$\color{red}{FST}$了...... ```python 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) ```