中国剩余定理+容斥原理。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=20; int T,p,cas=1,limit; LL L,R,A[maxn],B[maxn],h,a[maxn],b[maxn]; LL Extend_Euclid(LL a, LL b, LL&x, LL& y) { if(b==0) { x=1,y=0; return a; } LL d = Extend_Euclid(b,a%b,x,y); LL t = x; x = y; y = t - a/b*y; return d; } LL China_Reminder(int len, LL* a, LL* n) { int i; LL N = 1; LL result = 0; for(i = 0; i < len; i++) N = N*n[i]; for(i = 0; i < len; i++) { LL m = N/n[i]; LL x,y; Extend_Euclid(m,n[i],x,y); x = (x%n[i]+n[i])%n[i]; result = (result + m*a[i]*x%N)%N; } return result; } void dfs(int x,int s) { if(s==limit) { a[s]=7, b[s]=0; LL res=China_Reminder(s+1,b,a); if(res>R) return; LL rep=1; for(int i=0;i<=s;i++) rep*=a[i]; LL small,large; if(res>=L) small=0; else small=(L-res)%rep==0 ? ((L-res)/rep):((L-res)/rep+1); large=(R-res)/rep; h=h+large-small+1; return; } if(x==p+1) return; dfs(x+1,s); a[s]=A[x], b[s]=B[x]; dfs(x+1,s+1); } int main() { scanf("%d",&T); while(T--) { scanf("%d%lld%lld",&p,&L,&R); for(int i=1;i<=p;i++) scanf("%lld%lld",&A[i],&B[i]); LL sum=0,f=1; for(int i=1;i<=p;i++) limit=i, h=0, dfs(1,0), sum=sum+f*h, f=-f; printf("Case #%d: %lld ",cas++,R/7-(L-1)/7-sum); } return 0; }