题解 | 剩下的数

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int l, r;
        cin >> l >> r;
        int n = r - l + 1;
        long long sum_total = (long long)(l + r) * n / 2; // 避免整数溢出
        int m;
        cin >> m;
        while (m--) {
            int x;
            cin >> x;
            if (sum_total % x == 0) {
                cout << 0 << endl;
                continue;
            }
            if (n >= x) {
                cout << 1 << endl;
                continue;
            }
            bool has_valid_sub = false;
            for (int i = 0; i < n; ++i) {
                for (int j = i; j < n; ++j) {
                    long long sub_sum = (long long)(l + i + l + j) * (j - i + 1) / 2;
                    if (sub_sum % x == 0) {
                        has_valid_sub = true;
                        break;
                    }
                }
                if (has_valid_sub) break;
            }
            cout << (has_valid_sub ? 1 : n) << endl;
        }
    }
    return 0;
}