题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5768
给你n个同余方程组，然后给你l,r,问你l，r中有多少数%7=0且%ai != bi.
比较明显的中国剩余定理+容斥，容斥的时候每次要加上个(%7=0)这一组。
中间会爆longlong，所以在其中加上个快速乘法(类似快速幂)。因为普通的a*b是直接a个b相加，很可能会爆。但是你可以将b拆分为二进制来加a，这样又快又可以防爆。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
LL a[] , b[], fuck = 1e18; LL Fmul(LL a , LL n , LL mod) { //快速乘法
LL res = ;
while(n) {
if(n & ) {
res = (res + a) % mod;
}
a = a * % mod;
n >>= ;
}
return res;
} LL exgcd(LL a , LL b , LL &x , LL &y) {
LL res = a;
if(!b) {
x = ;
y = ;
}
else {
res = exgcd(b , a % b , x , y);
LL temp = x;
x = y;
y = temp - a / b * y;
}
return res;
} LL CRT(LL a[] , LL m[] , LL n) {
LL M = , res = ;
for(LL i = ; i <= n ; i++) {
M = M * m[i];
}
for(LL i = ; i <= n ; i++) {
LL x , y , Mi = M / m[i];
exgcd(Mi , m[i] , x , y);
x = (x % m[i] + m[i]) % m[i];
res = (res + Fmul(x * a[i] % M , Mi , M) + M) % M;
}
if(res < )
res += M;
return res;
} LL Get(LL n, LL x, LL y) {
if(x > n)
return ;
else {
n -= x;
return (LL)( + n / y);
}
} int main()
{
int t, n;
LL l , r , md[], di[];
scanf("%d", &t);
for(int ca = ; ca <= t; ++ca) {
scanf("%d %lld %lld", &n, &l, &r);
di[] = , md[] = ;
for(int i = ; i <= n; ++i) {
scanf("%lld %lld", a + i, b + i);
}
LL res1 = , res2 = ;
int limit = ( << n) - ;
for(int i = ; i <= limit; ++i) {
int temp = i, index = ;
LL mul = ;
for(int j = ; temp ; ++j) {
if(temp & ) {
di[++index] = a[j];
md[index] = b[j];
mul *= a[j];
}
temp >>= ;
}
if(index % ) {
res1 -= Get(l - , CRT(md, di, index), mul);
res2 -= Get(r, CRT(md, di, index), mul);
}
else {
res1 += Get(l - , CRT(md, di, index), mul);
res2 += Get(r, CRT(md, di, index), mul);
}
}
printf("Case #%d: %lld\n",ca, r/ - (l-)/ - (res2 - res1));
}
return ;
}