CF1715B 题解

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/CF1715B) [更好的阅读体验？](https://liangbowen.blog.luogu.org/solution-cf1715b) 看起来挺难，其实一分钟就能想出来。 ## 思路 首先考虑什么时候无解。由于 $k \times \left\lfloor\dfrac{a}{k}\right\rfloor \le a \le \left\lfloor\dfrac{a}{k}\right\rfloor + (k - 1)$，$a$ 与 $k$ 是自然数。' 所以可得下式。（看起来很复杂，其实很简单，要耐心看！） $$k \times \sum\limits_{i=1}^n\lfloor\frac{a_i}{k}\rfloor \le\sum\limits_{i=1}^na_i \le k \times \sum\limits_{i=1}^n\lfloor\frac{a_i}{k}\rfloor + n \times (k - 1)$$ 用原题中的 $b$ 和 $k$ 表示。 $$k \times b \le s \le k \times b + n \times (k - 1)$$ 不在这个范围内，就是无解了。 继续思考：在这个范围内就是有解，那怎么构造解呢？ 我们可以先满足 $b$，再满足 $s$。 满足 $b$ 非常简单，我们可以直接让 $a_1 = k \times b$。然后计算用掉 $a_1$ 后剩下的 $s$。 接下来，每一个 $a_i$ 都可以再塞 $0$ 到 $(k - 1)$。由于范围限制，最后一定是可以塞完的。那这题就做完啦。 ## 完整代码 ```cpp #include <iostream> #include <cstdio> #include <cstring> #define space putchar(' ') #define endl putchar('\n') using namespace std; typedef long long LL; typedef long double LD; void fastio() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); } LL read() { char op = getchar(); LL x = 0, f = 1; while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();} while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar(); return x * f; } void write(LL x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); } LL a[100005]; void solve() { LL n = read(), k = read(), b = read(), s = read(); if (b * k <= s && s <= b * k + n * (k-1)) { a[1] = b * k; LL left = s - b * k; for (int i = 1; i <= n; i++, space) { if (left >= k - 1) write(a[i] + k - 1), left -= (k - 1); else if (left != 0) write(a[i] + left), left = 0; else write(a[i]); } endl; } else puts("-1"); } int main() { int T = read(); while (T--) solve(); return 0; } ``` 其实也可以不用数组，思路是一样的。[代码](https://codeforces.com/contest/1715/submission/169474963)也差不了多少。 希望能帮助到大家！