• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1244C The Football Season

开发技术 开发技术 6小时前 1次浏览

CF1244C The Football Season

题意:

解方程组:(x+y+z=n) , (wx + dy = p) , 要求 (x ,y , z) 都非负。

(1 leqslant n leqslant 10^{12} , 1 leqslant p leqslant 10 ^ {17} , 1 leqslant d < w leqslant 10^5)

解法:

第一个式子等价于 $x + yleqslant n $ 。

而对于第二个式子,若存在一组解 (x_0 , y_0) 。则通解为:

(x = x_0 – kd)

(y = y_0 + kw)

于是我们发现 (x + y = x_0 + y_0 + k(w – d))

为了使 (x + y) 尽可能小,(k) 必须尽可能小 。且 (y) 非负,所以我们只需要在 (0 leqslant y < w) 的范围内找一组解就行了。

代码实现就直接枚举 (y)([0 , w – 1]) 之间,然后回代验证即可。

(x = frac{p-d cdot y}{w})

(z = n – x – y)

时间复杂度

很显然是 (O(w))

Code


程序员灯塔
转载请注明原文链接:CF1244C The Football Season
喜欢 (0)