# CF1244C The Football Season(CF1244C The Football Season)-其他

## CF1244C The Football Season(CF1244C The Football Season)

CF1244C The Football Season

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

$$x = x_0 – kd$$

$$y = y_0 + kw$$

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

$$z = n – x – y$$

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