题意：
给出x, y, m[1...n], a[1..n].
在[x,y]中寻找 p % 7 = 0 且对任意(1<= i <=n) p % m[i] != a[i] 的数字的个数
分析：
可用容斥定理，先在[x,y]找出所有7的倍数，再根据多个模线性方程连立，去掉所有不合法的
因 m[1...n] 互质，故可直接使用中国剩余定理.
并且需要在其中用 快速加法 防止超 long long
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define LL long long
const int MAXN = ;
LL ExtGcd(LL a,LL b,LL &x,LL &y)
{
if (b == ) {x = ; y = ; return a;}
LL d = ExtGcd(b, a%b, y, x);
y -= a / b * x;
return d;
}
LL Mul(LL a,LL b,LL MOD)
{
a%=MOD; b%=MOD;
LL res = ;
while(b)
{
if (b&) res = (res + a) % MOD;
a <<= ; if(a > MOD) a-=MOD;
b >>= ;
}
return res;
}
void CRT(LL &ans,LL &M, LL a[],LL m[],int k) //X = a[i] ( mod m[i] )(m[i]两两互质)
{ //解为 X = ans + M * t (0 <= ans <= M)
M = , ans = ;
LL x, y, Mi;
for (int i = ; i < k; i++) M *= m[i];
for (int i = ; i < k; i++)
{
Mi = M / m[i];
ExtGcd(m[i], Mi, x, y);
ans = (ans + Mul( Mul(y, Mi, M), a[i], M)) % M;
}
if(ans < ) ans += M;
}
int t, n;
LL x, y;
LL m1[MAXN], a1[MAXN], m[MAXN], a[MAXN];
LL Cal(LL m,LL a)
{
LL x0 = x + m - a;
LL y0 = y + m - a;
return y0 / m - (x0 - ) / m;//计算[x,y]中有多少p % m = a
}
int main()
{
scanf("%d", &t);
for(int tt = ; tt <= t; tt++)
{
scanf("%d%lld%lld", &n, &x, &y);
for(int i = ; i < n ; i++)
scanf("%lld%lld", &m1[i], &a1[i]);
int cnt = ;
LL ans = Cal(,);//找出所有7的倍数
for (int i = ; i < (<<n); i++)//枚举
{
cnt = ;
for (int j = ; j < n; j++)
{
if (i & (<<j))
{
m[cnt] = m1[j];
a[cnt] = a1[j];
++cnt;
}
}
m[cnt] = ;
a[cnt] = ;
++cnt;
LL M,A;
CRT(A, M, a, m, cnt);
if (cnt%) ans += Cal(M, A);//加奇数个,减偶数个
else ans -= Cal(M, A);
}
printf("Case #%d: %lld\n",tt,ans);
}
}