CF1244C The Football Season

洛谷链接

题意：求一组 $x,y(x + y \le n)$，使得 $w \cdot x + d \cdot y = p$。

看到这样的题，第一反应当然是用扩欧直接写。

然而本题数据规模太大，会导致 $\text{TLE}$。

换一种思路：题目中指明 $w \gt d$，从这个角度下手。

要让 $x+y \le n$，不难发现只要让 $y$ 尽量小即可。

观察发现，若方程有一组非负整数解，则一定存在一组非负整数解使得 $y \in [0,w)$。

证明：反证法。若 $y \ge w$，设 $y = w \cdot q + r(q \in N^{+},r \in [0,w - 1])$。

$\therefore w \cdot x + d \cdot (w \cdot q + r) = p$

$\therefore w \cdot x + w \cdot d \cdot q + d \cdot r = p$

$\therefore w \cdot (x + d \cdot q) + d \cdot r = p$。

故 $y = r$ 时，原方程有一组非负整数解。

 

那么我们只要从 $0$ 到 $w-1$ 枚举 $y$ 的值，算出对应的 $x$ 的值，判断一下是否合法即可。

代码：

 

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn = 100005;
 6 typedef unsigned long long ull;
 7 ull n,p,w,d;
 8 int main() {
 9     scanf("%llu%llu%llu%llu",&n,&p,&w,&d);
10     if(n * w < p) {
11         puts("-1");
12         return 0;
13     }
14     ull x,y;
15     for(y = 0;y < w;++ y) {
16         if(!((p - d * y) % w)) {
17             break ;
18         }
19     }
20     if(y >= w) {
21         puts("-1");
22         return 0;
23     }
24     x = (p - d * y) / w;
25     if(x + y > n) {
26         puts("-1");
27         return 0;
28     }
29     printf("%llu %llu %llu\n",x,y,n - x - y);
30     return 0;
31 } 

QAQ