Codeforces Round 592 (Div. 2) C题 The Football Season（Exgcd）
题目链接
https://codeforces.com/problemset/problem/1244/C
思路
其实就是要求 a x + b y = c ax+by=c ax+by=c的一组 x + y x+y x+y的最小整数解。因为题目保证了 a > b a>b a>b，所以只需要使得 y y y最小即可。
我们对 a x + b y = c ax+by=c ax+by=c推导得到： y = − a b x + c b y = -\frac{a}{b}x + \frac{c}{b} y=−bax+bc，如下图所示：
该图展示了为什么
y
y
y要取最小非负整数。
因此本题使用扩展欧几里得即可。
注意：本题会爆 l o n g l o n g longlong longlong，所以我直接用了 p y t h o n python python。
代码
def exgcd(a,b):
if b == 0:
return a,1,0
x1 = 0
y1 = 0
gcd = 0
gcd,x1,y1 = exgcd(b,a % b)
return gcd, y1, x1 - a // b * y1
n, p, w, d = map(int, input().split())
opgcd,x,y = exgcd(w, d)
if p % opgcd != 0:
print(-1)
exit(0)
p //= opgcd
w //= opgcd
d //= opgcd
x *= p
y *= p
miny = (y % w + w) % w
tx = x - (miny - y) // w * d
if tx >= 0 and miny >= 0 and tx + miny <= n:
print(f"{tx} {miny} {n - tx - miny}")
else:
print(-1)