CF1244C The Football Season

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