CF1244C-The Football Season

题面描述

The football season has just ended in Berland. According to the rules of Berland football, each match is played between two teams. The result of each match is either a draw, or a victory of one of the playing teams. If a team wins the match, it gets $w$ points, and the opposing team gets $0$ points. If the game results in a draw, both teams get $d$ points.

The manager of the Berland capital team wants to summarize the results of the season, but, unfortunately, all information about the results of each match is lost. The manager only knows that the team has played $n$ games and got pp points for them.

You have to determine three integers $x$, $y$ and $z$ — the number of wins, draws and loses of the team. If there are multiple answers, print any of them. If there is no suitable triple $(x,y,z)$, report about it.

输入格式

The first line contains four integers $n$, $p$, $w$ and $d\ (1 \le n \le 10^{12}, 0 \le p \le 10^{17}, 1 \le d < w \le 10^{5})$ — the number of games, the number of points the team got, the number of points awarded for winning a match, and the number of points awarded for a draw, respectively. Note that $w > d$, so the number of points awarded for winning is strictly greater than the number of points awarded for draw.

样例数据

样例输入1

30 60 3 1

样例输出1

17 9 4

样例输入2

10 51 5 4

样例输出2

-1

样例输入3

20 0 15 5

样例输出3

0 0 20

题解

读题很容易得出,若我们设赢得的场次为$x$,输掉的场次为$y$,那么就有:

$$
\\
\begin{cases}
xw+yd=p\\
x+y+z=n \rightarrow x+y\le n
\end{cases}
\\
$$

二元一次不等式,用拓展欧几里得算法(详见数论知识点整理)得到该方程的通解:

$$
\\x=x_0\times \frac{p}{gcd(w,d)}+k\times \frac{d}{gcd(w,d)} \\
y=y_0\times \frac{p}{gcd(w,d)}-k\times \frac{w}{gcd(w,d)}
\\
$$

观察题目输入得知,由于$w>d$,故显然,对于方程,当$y$取得最小值时,$x+y$取得最小值。因而如果原方程有解满足$x+y<n$,则当$y$取得非负最小值时一定满足$x+y<n$,即,此时的解是满足题目条件的解。

再观察$y$通解的形式,可以得知,每次改变$y$的值,$y$会变化$\frac{w}{gcd(w,d)}$。那么要取得$y$的非负最小值,只需要令$y$对$\frac{w}{gcd(w,d)}$取模就好。即:

$$
\\
y=(y+\frac{w}{gcd(w,d)})\ mod\ \frac{w}{gcd(w,d)}
$$

其中,加法用于保证非负。

这样我们取得的$y$值如果符合条件,则说明原方程有解,输出该$y$值下的$x,y,n-x-y$即可;否则,原方程无满足条件的解,输出$-1$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, p, w, d;

int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int r = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return r;
}

signed main() {
cin>>n>>p>>w>>d;
int x0, y0;
int Gd = exgcd(w, d, x0, y0);
if (p % Gd != 0) {
cout << "-1" << endl;
return 0;
}
int mod = w / Gd;
int x, y = y0;
y = ((y0 % mod) * (p / Gd % mod) % mod + mod) % mod;
x = (p - y * d) / w;
if (x + y > n || x < 0 || y < 0) {
cout << "-1" << endl;
return 0;
}
cout << x << " " << y << " " << n - x - y << endl;
return 0;
}

CF1244C-The Football Season
https://tridiamond.tech/post/CF1244C.html
作者
想变成一只白泽
发布于
2022年8月10日
许可协议