题解 | #剩下的数#

核心结论： 对于每一次询问 $x$ ，最终剩下的最少数量要么是 0，要么是 1。

推导过程：

整体和的性质： 每一次操作，牛牛都会删去一段和为 $x$ 的倍数的数。这意味着，无论删除了多少段，剩余数字的总和与初始数字的总和在模 $x$ 意义下是同余的。设初始所有数的和为 $S_{total}$ ，剩余数的和为 $S_{rem}$ 。因为删除部分的和 $\equiv 0 \pmod x$ ，所以 $S_{rem} \equiv S_{total} \pmod x$ 。
能否全部删完（答案为 0 的情况）： 如果初始总和 $S_{total}$ 本身就是 $x$ 的倍数（即 $S_{total} \equiv 0 \pmod x$ ），那么牛牛可以选择整个环作为一段（因为整个环的和是 $x$ 的倍数），直接一次性全部删去。此时剩余个数为 0。
能否只剩一个（答案为 1 的情况）： 如果 $S_{total}$ 不是 $x$ 的倍数，那么最后肯定不能删成 0 个（因为 0 个数的和为 0，是 $x$ 的倍数，这与同余性质矛盾）。那么最少能剩几个呢？

题目保证了 $x \le r-l+1$ （即 $x$ 小于等于环中数字的总个数）。环中的数字是连续整数 $l, l+1, \dots, r$ 。在一个长度至少为 $x$ 的连续整数序列中，必然包含模 $x$ 的所有余数（0 到 $x-1$ 各至少出现一次）。

我们需要剩下的数的和 $S_{rem} \equiv S_{total} \pmod x$ 。既然序列中包含了所有可能的余数，那么一定存在一个数字 $y$ （ $l \le y \le r$ ），使得 $y \equiv S_{total} \pmod x$ 。

操作策略： 我们保留这个数字 $y$ ，将环上除了 $y$ 以外的所有其他数看作一段（在环上，去掉一个点，剩下的部分依然是连续的一段）。这一段的和为 $S_{total} - y$ 。因为 $y \equiv S_{total} \pmod x$ ，所以 $S_{total} - y \equiv 0 \pmod x$ 。这意味着除了 $y$ 以外的那一段的和是 $x$ 的倍数，可以被一次性删去。

因此，只要 $S_{total}$ 不是 $x$ 的倍数，我们总是可以通过一次操作删去除了某一个特定数字外的所有数，最终只剩下 1 个数。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        ll l, r;
        cin >> l >> r;
        int m;
        cin >> m;
        ll S = (l + r) * (r - l + 1) / 2;
        while (m--) {
            ll x;
            cin >> x;
            if (S % x == 0)
                cout << "0\n";
            else
                cout << "1\n";
        }
    }
}