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

< strong > meaning of the question: < / strong >

Solve the equations: \ (x + y + Z = n \), \ (Wx + dy = P \), and it is required that \ (x, y, Z \) are non negative.

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

< strong > solution: < / strong >

The first expression is equivalent to $X + y \ leqslant n $.

For the second equation, if there is a set of solutions \ (x_0, y_0 \). The general solution is:

\(x = x_0 – kd\)

\(y = y_0 + kw\)

So we find that \ (x + y = x_0 + y_0 + K (W – D) \).

In order to make \ (x + y \) as small as possible, \ (K \) must be as small as possible. And \ (Y \) is non negative, so we only need to find a set of solutions within the range of \ (0 \ leqslant Y & lt; w \).

The code implementation directly enumerates \ (Y \) between \ ([0, W – 1] \), and then back verifies.

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

\(z = n – x – y\)

< strong > time complexity < / strong >

Obviously \ (O (W) \).

Code