题意：……应该不用我说了，看起来就很容斥原理，很中国剩余定理……
方法：因为题目中的n最大是15，使用状态压缩可以将所有的组合都举出来，然后再拆开成数组，进行中国剩余定理的运算，中国剩余定理能够求出同时满足余膜条件的最小整数x，x在（1，M）之间由唯一值，M是各个除数的乘积，所有符合条件的解为ans = x+k*M，可以知道在[1，R]这个区间内，有（M+R-x）/ M个k符合条件，然后在运算中为了防止溢出，所以使用了带膜乘法，就是将乘数转化为二进制，通过位移运算符，在中间过程中不断的取膜（看代码很容易明白）
注意：为了简化运算，把（7，0）这一组加进去，带膜乘法中，需要使用同余膜定理把乘数转化为整数，因为欧几里德算法有可能返回负数，不转化会陷入死循环，我之前忘了，结果……题目给的样例都已经死在了里面……
感悟：真不愧是多校训练赛，一个题目融合了这么多知识点。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 20
#define LL long long
int n,cnt;
LL X,Y,p[N],a[N],Pt[N],At[N];
int Get_Zuhe(int k){
int ip;
cnt = ip = ;
while(k){
if(k&){
Pt[cnt] = p[ip];
At[cnt] = a[ip];
cnt++;
}
ip++;
k >>= ;
}
Pt[cnt] = ;
At[cnt] = ;
cnt++;
return (cnt%);
}
LL ex_gcd(LL a,LL b,LL &x,LL &y){
if(b==) {
x=; y=;
return a;
}
LL R = ex_gcd(b,a%b,y,x);
y -= x*(a/b);
return R;
}
LL Mul(LL x,LL y,LL M){
LL ans = ;
while(y){
//cout<<y<<endl;
if(y&) ans = (ans+x%M)%M;
x = (x + x) % M;
y >>= ;
}
return ans;
}
LL China(){
LL M = ,m,ret = ,x,y,L,R;
for(int i = ;i < cnt;i++) M *= Pt[i];
for(int i = ;i < cnt;i++){
m = M/Pt[i];
ex_gcd(m,Pt[i],x,y);
x = (x+M)%M;///不要忘记转化为正数
ret = (ret+Mul(Mul(m,x,M),At[i],M)%M) % M;
}
ret = (ret+M)%M;
// printf("M = %I64d\n",M);
// printf("ret = %I64d\n",ret);
R = (Y+M-ret)/M;
L = (X-+M-ret)/M;
return R - L;
}
LL Solve(){
int tmp = (<<n),judge;
LL all = Y/ - (X-)/;
LL sum = ,ch;
for(int i = ;i < tmp;i++){
judge = Get_Zuhe(i);
ch = China();
// printf("china[%d] = %I64d\n",i,ch);
if(judge) sum -= ch;
else sum += ch;
}
return (all - sum);
}
int main(){
// freopen("A.in.cpp","r",stdin);
int t,ca = ;
scanf("%d",&t);
while(t--){
scanf("%d %I64d %I64d",&n,&X,&Y);
for(int i = ;i < n;i++){
scanf("%I64d %I64d",&p[i],&a[i]);
}
printf("Case #%d: %I64d\n",++ca,Solve());
}
return ;
}