题目描述
给定(n)对数，(p_i和a_i)。
求区间([L,R])间为(7)的倍数，同时满足对于所有的(p_i)取模后不为(a_i)的数的个数。
Input
第一行为整数 (T(T≤20)) 代表数据组数
每组数据的第一行为(3)个整数 (n, l, r(0<=n<=15,0<l<r<1e18))。
之后(n)行每行有两个数(p_i)和 (a_i)。
输入保证所有(p_i)互不相同且 (p_i!=7)。
输入保证(p_1*p_2*…*p_n<=1e18) 并且(0<a_i<p_i<=1e5)对所有$ i∈(1…n)$.成立
Output
对每个数据输出一行，先输出"Case #x: ",x=1,2,3…., 之后输出答案。
Sample Input
2
2 1 100
3 2
5 3
0 1 100
Sample Output
Case #1: 7
Case #2: 14
对于一组([L,R])可以转化为([1,R]-[1,L-1])。
那么我们就要求([1,x])间满足条件的数的个数。
我们发现最多只有(15)个限制条件，也就是说最多只有(2^{15})种限制情况。
我们考虑满足条件的数的个数为所有数-不满足条件的数的个数。
所有数我们十分好求，直接就是(x/7)即可。
那么我们需要求出不满足条件的数的个数。
我们考虑容斥求解，对于所有的限制条件我们会计算重复。
那么我们对于其中的一部分条件进行计算，最后进行容斥统计即可。
对于当前的限制条件，我们要求出满足所有限制条件的数的个数。
所以我们可以把所有的限制条件转化为一个大的限制条件。
[egin{cases}
Ans=res_1\%p_1 \
Ans=res_2\%p_2 \
Ans=res_3\%p_3 \
Ans=res_4\%p_4
end{cases}
]
我们直接利用中国剩余定理求解即可。
最后我们得到了一个方程的解集(Ans+k*M).
那么区间([1,L])内的不满足条件的数的个数为(1+(L-Ans)/M)。
在原来的(tot)上减去即可。
一个需要注意的是，若(Ans>L)，则说明该区间内无解，需要直接(continue)掉
#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
#define reg register
#define clr(a,b) memset(a,b,sizeof a)
#define Mod(x) (x>=mod)&&(x-=mod)
#define abs(a) ((a)<0?-(a):(a))
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define debug2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])
#pragma GCC optimize(2)
inline int Read(void) {
int res=0,f=1;
char c;
while(c=getchar(),c<48||c>57)if(c=='-')f=0;
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>=48&&c<=57);
return f?res:-res;
}
template<class T>inline bool Min(T &a, T const&b) {
return a>b?a=b,1:0;
}
template<class T>inline bool Max(T &a, T const&b) {
return a<b?a=b,1:0;
}
const int N=525,M=1e5+5;
bool MOP1;
int n,m,k,A[N],P[N],res[N],mod[N],a[N],pos[N];
int Exgcd(int a, int b, int &x, int &y) {
if(!b) {
x=1,y=0;
return a;
}
int g=Exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
int Mod,tot;
inline int Excrt(void) {
int M=mod[1],ans=res[1],x,y;
rep(i,2,tot) {
int g=Exgcd(M,mod[i],x,y);
x*=(res[i]-ans)/g,y=mod[i]/g,x=(x%y+y)%y;
ans=M*x+ans,M=M/g*mod[i],ans%=M;
}
int z=(ans%M+M)%M;
Mod=M;
return z;
}
int solve(int x) {
if(!x)return 0;
int Res=x/7;
ret(i,1,1<<n) {
tot=0;
rep(j,1,n)if(i&(1<<j-1))mod[++tot]=P[j],res[tot]=A[j];
mod[++tot]=7,res[tot]=0;
int Now=Excrt();
if(Now>x)continue;
if(tot%2)Res+=(x-Now)/Mod+1;
else Res-=(x-Now)/Mod+1;
}
return Res;
}
int vis[N];
bool MOP2;
inline void _main(void) {
int T=Read(),Case=0;
while(T--) {
n=Read();
int l=Read(),r=Read();
rep(i,1,n)P[i]=Read(),A[i]=Read();
printf("Case #%lld: %lld
",++Case,solve(r)-solve(l-1));
}
}
signed main() {
_main();
return 0;
}