Bluefissure's Blog

A Place for Recording

0%

HDU 5768 Lucky7 数论 中国剩余定理

Posted on Edited on In Disqus:

2016 Multischool-Training-4-1005

题目链接

题意：

给个区间\(\left\[ x,y \right\] \) ， \(x,y\) 范围在 \({ 10 }^{ 18 }\) 。

求问区间内有多少数能被7整除，并且对任意\({ p }_{ i }\)取模不等于\({ a }_{ i }\)。

思路：

先算出来被7整除的数的个数，然后对\({ p }_{ i }\)和\({ a }_{ i }\)容斥一下，奇减偶加就好，对于多个同余方程组成的同余方程组：\(\begin{cases} x\equiv { a }_{ 1 }\left( mod\quad { p }_{ 1 } \right)  \\ x\equiv { a }_{ 2 }\left( mod\quad { p }_{ 2 } \right)  \\ ... \\ ... \\ x\equiv { a }_{ k }\left( mod\quad { p }_{ k } \right)  \end{cases}\) 用中国剩余定理求解及统计个数。

需要注意的是在中国剩余定理的过程中可能爆long long，乘法的过程要改成快速乘。(WA了两发QAQ)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
#define LL long long
#define MAXN 100
int n;
LL p[MAXN],a[MAXN],x,y;
bool op[MAXN];
LL dfsans=0;
LL lcm(LL a,LL b)
{
    return a/__gcd(a,b)*b;
}
LL mul(LL a,LL b,LL c)
{
    a%=c;
    b%=c;
    LL ret=0;
    while(b){
        if(b&1){
            ret+=a;ret%=c;
        }
        a<<=1;
        if(a>=c) a%=c;
        b>>=1;
    }
    return ret;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(a==0&&b==0) return -1;
    if(!b){
        x=1;y=0;
        return a;
    }
    LL ans=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return ans;
}
LL China(int k)
{
    LL M=1,Mi,x0,y0,d,ans=0;
    for(int i=0;i<=k;i++)
        if(op[i]) M*=p[i];
    for(int i=0;i<=k;i++){
        if(!op[i]) continue;
        Mi=M/p[i];
        exgcd(Mi,p[i],x0,y0);
        (x0+=M)%=M;
        LL tt=mul(Mi,x0,M);
        (ans+=mul(tt,a[i],M))%=M;
    }
    while(ans<0) (ans+=M)%=M;
    return ans;
}
LL sol(int n,LL x)
{
    LL base=China(n);
    LL LCM=1;
    for(int i=0;i<=n;i++)
        if(op[i])
            LCM=lcm(LCM,p[i]);
    if(x<base) return 0;
    return (x-base)/LCM+1;
}
void dfs(int idx,LL x)
{
    if(idx==1)
        dfsans=0;
    if(idx>n){
        int c=0;
        for(int i=0;i<=n;i++){
            if(op[i]){
                c++;
            }
        }    
        LL tmp=sol(n,x);
        if(c&1) dfsans+=tmp;
        else dfsans-=tmp;
        return;
    }
    op[idx]=0;
    dfs(idx+1,x);
    op[idx]=1;
    dfs(idx+1,x);
}
void solve(int n,LL x,LL y)
{
    LL LCM=1;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&p[i],&a[i]);
    p[0]=7;a[0]=0;
    op[0]=1;
    LL cnt1=0,cnt2=0;
    dfsans=0;
    dfs(1,x-1);
    cnt1=dfsans;
    dfsans=0;
    dfs(1,y);
    cnt2=dfsans;
    printf("%lld\n",cnt2-cnt1);
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%d",&n);
        scanf("%lld%lld",&x,&y);
        printf("Case #%d: ",cas);
        solve(n,x,y);
    }
    return 0;
}