題目連結:http://acm.split.hdu.edu.cn/showproblem.php?pid=5768
題意:給出n對(p,a),求區間[L,R]内為7的倍數,且不滿足任意i∈n, x % pi = ai的個數。
思路:容斥定理,設單獨事件Ai為區間内為7的倍數且滿足x % pi = ai的個數。那麼區間内7的倍數的個數 - A1∪A2∪A3...∪Ai即為答案。然後計算過程中需要借助中國剩餘定理計算出最小滿足條件的數進而得到滿足目前條件的數的個數。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <utility>
using namespace std;
#define rep(i,j,k) for (int i=j;i<=k;i++)
#define Rrep(i,j,k) for (int i=j;i>=k;i--)
#define Clean(x,y) memset(x,y,sizeof(x))
#define LL long long
#define ULL unsigned long long
#define inf 0x7fffffff
#define mod 100000007
const int maxn = 20;
int n;
LL L,R;
LL prime[maxn],ret[maxn];
LL exgcd( LL a , LL b , LL &x , LL &y )
{
if ( b == 0 )
{
x = 1 , y = 0;
return a;
}
LL r = exgcd( b , a % b , y , x );
y -= x * ( a / b );
return r;
}
LL gcd( LL a , LL b )
{
return b==0?a:gcd(b,a%b);
}
// X 同餘 a[i] ( mod m[i] ) ,有n個式子(ai,mi),求X
LL CRT( LL a[] , LL m[] , int n )
{
LL M = m[0];
LL R = a[0];
rep(i,1,n)
{
LL d = gcd(M,m[i]);
LL c = a[i] - R;
if ( c % d ) return -1; //無解
LL x,y;
exgcd(M/d,m[i]/d,x,y);
x = ( c / d * x )%(m[i]/d);
R = R + x * M;
M = M / d * m[i];
R %= M;
}
if ( R < 0 ) R += M;
return R;
}
LL cal( LL N )
{
if ( N == 0 ) return 0;
LL p[maxn] , a[maxn];
LL ans = N/7;
int uplim = (1<<n)-1;
p[0] = 7 , a[0] = 0;
rep(i,1,uplim)
{
int num = 0;
LL sum = 7;
rep(j,1,n)
if( i & 1<<(j-1) ) sum *= prime[j] , num++ , p[num] = prime[j] , a[num] = ret[j];
LL st = CRT( a , p , num ); //最小滿足條件的數
if ( st == -1 ) continue;
int first = st <= N;//首個數是否在範圍内
if ( num & 1 ) ans -= max( 0LL , (N - st) ) / sum + first;
else ans += max( 0LL , (N - st) ) / sum + first;
}
return ans;
}
void init()
{
scanf("%d %I64d %I64d",&n,&L,&R);
prime[0] = 7 , ret[0] = 0;
rep(i,1,n) scanf("%I64d%I64d",&prime[i],&ret[i]);
}
int main()
{
int T;
cin>>T;
rep(cas,1,T)
{
printf("Case #%d: ",cas);
init();
printf("%I64d\n", cal(R) - cal(L-1) );
}
return 0;
}