题意：求满足7的倍数，不满足其他条件num % p == a 的num的个数。
思路：利用中国剩余定理我i们可以求出7的倍数，但是多算了不满足约定条件又得减去一个，但是又发现多减了，又得加回来。如此，那么应该应用容斥原理来解决问题。那么就应该是将所有的状态都遍历一下，然后根据1的个数来判断是不是+-号。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; const int maxn = ;
ll n, l, r;
ll m[maxn], a[maxn], f[maxn]; ll ex_gcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = ;
y = ;
return a;
} else {
ll tmp = ex_gcd(b, a%b, y, x);
y -= a / b * x;
return tmp;
}
} inline ll cnt(ll k, ll m, ll x) {
return (m - k + x) / m;
} ll mul(ll a, ll b, ll m) {
ll ans = ;
while(b) {
if(b&1LL) {
ans += a;
ans %= m;
}
a <<= ;
a %= m;
b >>= ;
}
return ans;
}
ll crt(int n, ll l, ll r) {
ll M = ;
for(int i = ; i < n; i++)
if(f[i])
M *= m[i]; ll ans = ;
for(int i = ; i < n; i++)
if(f[i]) {
ll mi = M / m[i];
ll mf, tmp;
ex_gcd(mi, m[i], mf, tmp);
mf = (mf % m[i] + m[i]) % m[i]; ans += mul(mul(a[i], mi, M), mf, M);
ans = (ans % M + M) % M;
}
return cnt(ans, M, r) - cnt(ans, M, l-);
} int main() {
int T;
scanf("%d", &T);
for(int ncase = ; ncase <= T; ncase ++) {
scanf("%lld%lld%lld", &n, &l, &r);
for(int i = ; i < n; i ++) {
scanf("%lld%lld", &m[i], &a[i]);
}
ll ans = ;
m[n] =; a[n] = ; f[n] = ;
for(int i = ; i < ( << n); i ++){
int tmp = i, cn = ;
for(int j = ; j < n; j ++){
if(tmp & ) {
f[j] = ; cn ++;
}else{
f[j] = ;
}
tmp >>= ;
}
if(cn & ) ans -= crt(n + , l, r);
else ans += crt(n + , l, r);
}
printf("Case #%d: %lld\n",ncase,ans);
}
return ;
}