题解：P16228 [蓝桥杯 2026 省 A] 读取指令

· · 题解

首先 w=0 直接输出 0，真的很阴。（哭）

显然如果 w 不能被 C 整除，或者 \dfrac w C>\dfrac{n(n+1)}{2}，此时显然无法凑出 w，答案为 -1。

下面证明：w\in\{1,2\}。

只要说明在集合 A=\{1,2,\dots,n\} 中挑出若干个数一定能凑出任意一个 x\in\left\{1,2,\dots,\dfrac{n(n+1)}{2}\right\} 即可，注意到：

因此区间数最多为 2，下面只要判断是否可以在 A 中取一个连续的区间，其和等于 \dfrac w C 即可。

设这个区间为 [i+1,i+N]，两个变量的取值范围是 i=0,1,\dots,n-1，N = 1,2,\dots,n-i，这个区间和为

\sum_{j=1}^N(i+j)=Ni+\dfrac{N(N+1)}2=\dfrac w C

如果从中想给定 i 后确定 N 比较复杂，需要解一个二次方程，不过可以在给定 N 的情况下确定 i，只需要：

i = \dfrac{\dfrac w C-N^2-N}{2N} \in\{0,1,\dots,n-N\}

即可。

参考代码：

#include <bits/stdc++.h>
#define int long long 

using namespace std;

inline int read() { 
    int num = 0, nev = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {  if (ch == '-') nev = -1; ch = getchar();}   
    while (ch >= '0' && ch <= '9') { num += ch - '0'; num *= 10; ch = getchar();}
    return num / 10 * nev;
}

signed main() {

    int T = read();
    while (T --) {
        int n = read(), c = read(), w = read();
        if (!w) {
            cout << w << endl;
            continue;
        }
        if (w % c) {
            puts("-1");
            continue;
        }
        w /= c;
        if (w > n * (n + 1) / 2) {
            puts("-1");
            continue;
        }
        int ans = 2;
        for (int N = 1; N <= n && N * N + N <= 2 * w; N ++) {
            if ((2 * w - N * N - N) % (2 * N) == 0 && (2 * w - N * N - N) / (2 * N) + N <= n) {
                ans = 1;
                break;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}