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<=105for 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

 

Sample Output

 

Author

FZU

 

Source

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll __int64

#define esp 0.00000000001

const int N=1e2+,M=1e6+,inf=1e9+,mod=;

ll a[N];

ll b[N];

ll p[N];

ll m[N];

ll mulmod(ll x,ll y,ll m)

{

    ll ans=;

    while(y)

    {

        if(y%)

        {

            ans+=x;

            ans%=m;

        }

        x+=x;

        x%=m;

        y/=;

    }

    ans=(ans+m)%m;

    return ans;

}

void exgcd(ll a, ll b, ll &x, ll &y)

{

    if(b == )

    {

        x = ;

        y = ;

        return;

    }

    exgcd(b, a % b, x, y);

    ll tmp = x;

    x = y;

    y = tmp - (a / b) * y;

}

ll CRT(ll a[],ll m[],ll n)

{

    ll M = ;

    ll ans = ;

    for(ll i=; i<n; i++)

        M *= m[i];

    for(ll i=; i<n; i++)

    {

        ll x, y;

        ll Mi = M / m[i];

        exgcd(Mi, m[i], x, y);

        //ans = (ans + Mi * x * a[i]) % M;

        ans = (ans +mulmod( mulmod( x , Mi ,M ), a[i] , M ) ) % M;

    }

    ans=(ans + M )% M;

    return ans;

}

int main()

{

    ll x,y,z,i,t;

    int T,cas=;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%I64d%I64d%I64d",&x,&y,&z);

        for(i=;i<=x;i++)

        scanf("%I64d%I64d",&b[i],&a[i]);

        ll ans=;

        for(i=;i<(<<x);i++)

        {

            ll cnt=,mul=;

            p[cnt]=;

            m[cnt++]=;

            for(int ji=,t=i;t>;t>>=,ji++)

            if(t&)mul*=b[ji],p[cnt]=a[ji],m[cnt++]=b[ji];

            ll pp=CRT(p,m,cnt);

            if(cnt&)

            ans+=z/mul+(z%mul>=pp)-((y-)/mul+(((y-)%mul)>=pp));

            else

            ans-=z/mul+(z%mul>=pp)-((y-)/mul+(((y-)%mul)>=pp));

        }

        printf("Case #%d: %I64d\n",cas++,ans);

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll __int64

#define esp 0.00000000001

const int N=1e2+,M=1e6+,inf=1e9+,mod=;

ll a[N];

ll b[N];

ll ji;

ll mulmod(ll x,ll y,ll m)

{

    ll ans=;

    while(y)

    {

        if(y%)

        {

            ans+=x;

            ans%=m;

        }

        x+=x;

        x%=m;

        y/=;

    }

    ans=(ans+m)%m;

    return ans;

}

void exgcd(ll a, ll b, ll &x, ll &y)

{

    if(b == )

    {

        x = ;

        y = ;

        return;

    }

    exgcd(b, a % b, x, y);

    ll tmp = x;

    x = y;

    y = tmp - (a / b) * y;

}

ll CRT(ll p,ll m,ll k,ll l)

{

    ll M = m * l;

    ll ans = ;

    ll x, y;

    ll Mi = l;

    exgcd(Mi, m, x, y);

    ans = (ans + mulmod( mulmod( x%M, Mi%M, M) , p%M , M))% M;

    Mi = m;

    exgcd(Mi, l, x, y);

    ans = (ans + mulmod( mulmod(x%M ,Mi%M , M) , k%M, M))% M;

    if(ans < ) ans += M;

    return ans;

}

void dfs(ll p,ll m,ll pos,ll step,ll x,ll &ans)

{

    if(pos==ji)

    {

        if(step%)

        {

            ans-=x/m;

            if(x%m>=p)

                ans--;

        }

        else

        {

            ans+=(x/m);

            if(x%m>=p)

                ans++;

        }

        return;

    }

    dfs(CRT(p,m,a[pos],b[pos]),m*b[pos],pos+,step+,x,ans);

    dfs(p,m,pos+,step,x,ans);

}

int main()

{

    ll x,y,z,i,t;

    int T,cas=;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%I64d%I64d%I64d",&x,&y,&z);

        ji=x;

        for(i=; i<x; i++)

        scanf("%I64d%I64d",&b[i],&a[i]);

        ll ansr=,ansl=;

        dfs(,,,,z,ansr);

        dfs(,,,,y-,ansl);

        printf("Case #%d: %I64d\n",cas++,ansr-ansl);

    }

    return ;

}