2016多校訓練Contest4: 1005 Lucky7 hdu5768

Problem Description 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.  

Input On the first line there is an integer T(T≤20) representing the number of test cases.

Each test case starts with three integers three intergers n, x, y(0<=n<=15,0<x<y< 1018 ) on a line where n is the number of pirmes. 

Following on n lines each contains two integers pi, ai where pi is the pirme and ?? abhors the numbers have a remainder of ai when they are divided by pi. 

It is guranteed that all the pi are distinct and pi!=7. 

It is also guaranteed that p1*p2*…*pn<= 1018  and 0<ai<pi<= 105 for every i∈(1…n).

Output For each test case, first output "Case #x: ",x=1,2,3...., then output the correct answer on a line.  

Sample Input

2
2 1 100
3 2
5 3
0 1 100
        

Sample Output

Case #1: 7
Case #2: 14



   
    
     Hint
    For Case 1: 7,21,42,49,70,84,91 are the seven numbers.
For Case2: 7,14,21,28,35,42,49,56,63,70,77,84,91,98 are the fourteen numbers.
   
        

算是CRT闆子題..？

加一個7，0的因子和餘數

然後對于n+1對枚舉選取的可能性跑CRT

算出結果後用容斥原理計算一下就可以了

因為為炸long long是以中間乘法要用快速乘做

#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct number
{
    unsigned __int64 x,p;
}a[101];
unsigned __int64 fast_multi(unsigned __int64 m, unsigned __int64 n, unsigned __int64 mod)//快速乘法
{
    unsigned __int64 ans = 0;//注意初始化是0，不是1
    while (n)
    {
        if (n & 1)
            ans += m;
        m = (m + m) % mod;//和快速幂一樣，隻不過這裡是加
        m %= mod;//取模，不要超出範圍
        ans %= mod;
        n >>= 1;
    }
    return ans;
}
unsigned __int64 power(unsigned __int64 x,unsigned __int64 y,unsigned __int64 mod){
    unsigned __int64 xt=1;
    while(y!=0){
        if(y%(unsigned __int64)2==1){
            xt=fast_multi(xt,x,mod);
        }
        x=fast_multi(x,x,mod);
        y=y/(unsigned __int64)2;
    }
    return xt;
}
struct answ{
    unsigned __int64 x;
    unsigned __int64 m,f;
}ansx[100001];
int b[101];
unsigned __int64 m[1001];
inline answ CRT(){
    unsigned __int64 M=1;
    answ ret;
    ret.x=0;
    int i;
    for(i=1;i<=n+1;i++)
        if(b[i]==1)
            M*=a[i].p;
    for(i=1;i<=n+1;i++)
        if(b[i]==1)
            m[i]=M/a[i].p;
    for(i=1;i<=n+1;i++)
        if(b[i]==1)
            ret.x= (ret.x+ fast_multi(a[i].x,fast_multi(m[i],power(m[i],a[i].p-2,a[i].p),M),M) )%M;
    ret.m=M;
    return ret;
}
int p;
inline void prepare(){
    p=0;
    memset(b,0,sizeof(b));
    b[n+1]=1;
    while(b[0]==0)
    {
        p++;
        ansx[p]=CRT();
        int i,sx=0;
        for(i=1;i<=n+1;i++)
            sx+=b[i];
        if(sx%2==0)
            ansx[p].f=0;
        else
            ansx[p].f=1;
        int j=n;
        while(b[j]==1)
        {
            b[j]=0;
            j--;
        }
        b[j]++;
    }
}
inline unsigned __int64 cale(__int64 x)
{
    unsigned __int64 ans=0;
    int i;
    for(i=1;i<=p;i++)
    {
        if(x<ansx[i].x)
            continue;
        if(ansx[i].f==1)
            ans=ans+(x-ansx[i].x)/ansx[i].m+1;
        else
            ans=ans-(x-ansx[i].x)/ansx[i].m-1;
    }
    return ans;
}
int main()
{
    int k=0;
    int T;
    scanf("%d",&T);
    while(T>0)
    {
        k++;
        T--;
        __int64 l,r;
        scanf("%d",&n);
        scanf("%I64u%I64u",&l,&r);
        int i;
        for(i=1;i<=n;i++)
            scanf("%I64d%I64d",&a[i].p,&a[i].x);
        a[n+1].p=7;
        a[n+1].x=0;
        prepare();
        printf("Case #%d: ",k);
        printf("%I64u\n",cale(r)-cale(l-1));
    }
    return 0;
}