Bluefissure's Blog

A Place for Recording

0%

HDU 5768 Lucky7 数论 中国剩余定理

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;
}