HDU 5768 Lucky7 容斥原理+中国剩余定理（互质）

分析：

因为满足任意一组pi和ai，即可使一个“幸运数”被“污染”，我们可以想到通过容斥来处理这个问题。当我们选定了一系列pi和ai后，题意转化为求[x，y]中被7整除余0，且被这一系列pi除余ai的数的个数，可以看成若干个同余方程联立成的一次同余方程组。然后我们就可以很自然而然的想到了中国剩余定理。需要注意的是，在处理中国剩余定理的过程中，可能会发生超出LongLong的情况，需要写个类似于快速幂的快速乘法来处理。

吐槽：赛场上不会快速乘，导致疯狂WA,唉，还是太年轻

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef  long long LL;
const int N = 20;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+7;
void exgcd(LL a,LL b,LL &d,LL& x,LL& y)
{
    if(!b)
    {
        d=a;
        x=1;
        y=0;
    }
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
LL a[20],m[20];
/*对应的模线性方程组，余数放在a数组，模数放在m数组*/
LL qpow(LL a,LL b,LL mod){
  a%=mod;
  LL ret=0;
  while(b){
    if(b&1)ret=(ret+a)%mod;
    b>>=1;
    a=(a+a)%mod;
  }
  return ret;
}
LL china(int n,LL* a,LL *m)
{
    LL M=1,d,y,x=0;
    for(int i=0; i<n; ++i)M*=m[i];
    for(int i=0; i<n; ++i)
    {
        LL w=M/m[i];
        exgcd(m[i],w,d,d,y);
        x=(x+qpow(qpow(y,w,M),a[i],M))%M;
    }
    return (x+M)%M;
}
LL p[N],yu[N];
int main(){
  int kase=0,n,T;
  scanf("%d",&T);
  while(T--){
    LL l,r;
    scanf("%d",&n);
    cin>>l>>r;
    for(int i=0;i<n;++i)
     cin>>p[i]>>yu[i];
    int len=(1<<n);
    LL ret=r/7-(l-1)/7;
    for(int i=1;i<len;++i){
       int cnt=0;
       LL cur=1;
       for(int j=0;j<n;++j){
          if(i&(1<<j)){
             m[cnt]=p[j];
             a[cnt]=yu[j];
             cnt++;
             cur*=p[j];
          }
       }
      m[cnt]=7;a[cnt]=0;
      cur*=7;
      cnt++;
      LL tmp=china(cnt,a,m);
      LL sub=0;
      if(tmp>=l&&tmp<=r){
        LL cha=r-tmp;
        sub=cha/cur+1;
      }
      else if(tmp<l){
         LL cha=l-tmp;
         tmp+=cha/cur*cur;
         if(tmp<l)tmp+=cur;
         if(tmp>=l&&tmp<=r){
          cha=r-tmp;
          sub=cha/cur+1;
         }
      }
      if(cnt&1)ret+=sub;
      else ret-=sub;
    }
    printf("Case #%d: %I64d
",++kase,ret);
  }
  return 0;
}