CF1244C The Football Season

本文主要是介绍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 + y\leqslant 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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程