hdu_5768 Lucky7

题目:

  When ?? was born, seven crows flew in and stopped beside him. In its childhood, ?? had been unfortunately fall into the sea. While it was dying, seven dolphins arched its body and sent it back to the shore. It is said that ?? used to surrounded by 7 candles when he faced a extremely difficult problem, and always solve it in seven minutes.
  ?? once wrote an autobiography, which mentioned something about himself. In his book, it said seven is his favorite number and he thinks that a number can be divisible by seven can bring him good luck. On the other hand, ?? abhors some other prime numbers and thinks a number x divided by pi which is one of these prime numbers with a given remainder ai will bring him bad luck. In this case, many of his lucky numbers are sullied because they can be divisible by 7 and also has a remainder of ai when it is divided by the prime number pi.
  Now give you a pair of x and y, and N pairs of ai and pi, please find out how many numbers between x and y can bring ?? good luck.

思路:

  首先很明显求小于的数中满足的个数就等于
  求解时可以求出不满足的数,剩下的就都是满足的了。但是求满足的个数并不好求,所以可以用容斥转化成求满足的个数,这样的话直接列出方程组即可。
  要求是七的倍数的限制也可以作为一条方程加入方程组。

代码:

#include <bits/stdc++.h>
#define ll long long
#define DEBUG(a) cerr<<"DEBUG:"<<#a<<'='<<(a)<<endl
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll calc(ll a,ll b,ll c){
    ll d,x,y;
    exgcd(a,b,d,x,y);
    if(c%d)return -1;
    b/=d;c/=d;
    return (x*c%b+b)%b;
}
struct CRT{
    ll A,M;
    CRT(){A=0;M=1;}
    bool insert(ll a,ll m){
        ll k=calc(M,m,a-A);
        if(!~k)return false;
        A+=M*k;
        M=lcm(M,m);
        return true;
    }
};
ll a[20],m[20],ans,l,r;
int n;
ll calc(ll x,CRT crt){
    if(x<crt.A)return 0;
    return (x-crt.A)/crt.M+1;
}
void dfs(int p,int now,CRT crt){
    if(p&1)
        ans-=calc(r,crt)-calc(l-1,crt);
    else
        ans+=calc(r,crt)-calc(l-1,crt);
    for(int i=now+1;i<=n;i++){
        CRT tmp=crt;
        if(tmp.insert(a[i],m[i]))
            dfs(p+1,i,tmp);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        CRT crt;
        scanf("%d%lld%lld",&n,&l,&r);
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",m+i,a+i);
        ans=r/7-(l-1)/7;
        crt.insert(0,7);
        for(int i=1;i<=n;i++){
            CRT tmp=crt;
            if(tmp.insert(a[i],m[i]))
                dfs(1,i,tmp);
        }
        printf("Case #%d: %lld\n",t,ans);
        end:;
    }
    return 0;
}