题解 | #剩下的数#

tag：鸽巢原理

令，根据可以有下面两种情况：

• 如果，那么可以把所有数都选了；
• 否则，那么我们是否可以找到一个数取模等于呢？结论是一定可以的，将都对取模，因为，所以区间对取模后会包含所有，所以我们一定可以找到一个数，所以最终只会剩下这一个数。

因此如果，输出1；否则输出0。

#include <iostream>
using namespace std;
using ll=long long;
int main() {
    int _;
    cin >> _;
    while(_--){
        ll l,r;
        cin >> l >> r;
        int m;
        cin >> m;
        while(m--){
            ll x;
            cin >> x;
            ll s=(l+r)*(r-l+1)/2;
            if(s%x==0) cout << 0 << endl;
            else cout << 1 << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")