Steven_MengのBlog

传送门

首先,附送本题数据生成器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
inline int gen(){
return (rand()<<15)|(rand());
}
int main(){
srand(time(NULL));
freopen("yukideru.in","w",stdout);
int n=100000,m=100000;
printf("%d %d\n",n,m);
for (register int i=1;i<=n;++i){
printf("%d ",gen()%1000000000);
}
printf("\n");
for (register int i=1;i<=m;++i){
int l=gen()%n+1,r=gen()%n+1;
if (l>r) swap(l,r);
printf("%d %d\n",l,r);
}
}

$Pro$

珂朵莉给你了一个长为$n$的序列,有$m$次查询,每次查询一段区间的乘积的约数个数$\mod 19260817$的值

$n,m\le 100000$
$1 \le a_i \le 1000000000$

$Sol$

首先,根据小学奥数(雾),设$D(x)$为$x$的约数个数,设$x=\prod p_i^{k_i} (p_i \in \text{prime})$,我们有

$D(x)=\prod (k_i+1)$。

于是,每次莫队转移的时候,我们把新加进的那个数(设为$A$)分解质因数,假设现在分解出了一个质数$p$,那么答案$\times inv(cnt[p]+1)$,然后$cnt[p]++$,最后$\times (cnt[p]+1)$,但是这样肯定会炸掉,因为质因数很多,考虑到$A$的质因数很多都是$<1000$,根据其他题解中的说法:$a$最多也只有两个$>1000$的质因数。

所以,方法就有了,考虑把$<1000$的和$\geq 1000$的质数分开考虑,因为$<1000$的质数只有$169$个,所以每次重新算也没有关系,$\geq 1000$的质数就按照上面方法维护就可以了。


再看怎么具体实现,首先预处理逆元和线性筛质数都是必须的

$1.$考虑维护$<1000$的质数对答案的贡献,维护一个前缀和数组$sum$,其中$sum[i][p]$代表$\prod_{j=1}^{i} a_j$中$p$出现的次数,求$\prod_{j=l}^{r} a_j$中$p$出现的次数,就是前缀和做一下差,即$sum[r][p]-sum[l-1][p]$。

$2.$考虑维护$\geq 1000$的质数对答案的贡献,由于$\geq1000$的质数比较多,不好记录,又发现其实答案只和$k_i$有关,和$p_i$是没关的,所以只要统计不同的数的个数即可,我们这里用一种比较偷懒的办法,新来一个数,我们把它扔进一个$map$里面,如果他出现过,那么记录他在$map$里面的编号,否则新建一个编号,这样就起到去重和离散化的效果(这种办法太偷懒了,导致程序效率不高),最后像上面说的一样,莫队维护一下。


注意:中间量要开$\text{long long}$,使劲卡常,此代码多交几次或许能$\rm AC$

时间复杂度$O(n \sqrt{n}*169)$


总结一下,质数在一段区间的稠密度是不同的,标程就是根据这个性质,分布稠密的小范围暴力搞,分布稀疏的大范围莫队搞,这是一种重要的思想。

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
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define MOD 19260817
#define MAXN 200005
#define MAXP 32005
#define CNT 169 //小于1000的质数个数
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
//思路:把<1000的和>=1000的分开考虑
static int inv[MAXN];
static int nprime[MAXN];
static int cnt,prime[MAXN],pos[MAXN];//预处理逆元,筛质数,初始化莫队
inline int ksm(int b,int k){
int ans=1;
while (k){
if (k&1) ans=((long long)ans*(long long)b)%MOD;
b=((long long)b*(long long)b)%MOD;
k>>=1;
}
return ans;
}
inline void Init(int n){
for (register int i=0;i<MAXN;++i){
inv[i]=ksm(i,MOD-2)%MOD;
}

for (register int i=2;i<MAXP;++i){
if (!nprime[i]){
for (register int j=i*2;j<MAXP;j+=i){
nprime[j]=true;
}
}
}
for (register int i=2;i<MAXP;++i){
if (!nprime[i]) prime[++cnt]=i;
}

int Size=sqrt(n);
for (register int i=1;i<=n;++i){
pos[i]=(i-1)/Size+1;
}
}

static int sum[MAXN][CNT];
static int v[MAXN][CNT],top[MAXN];
static map<int,int>M;//暂时没有想到好的方法替代这个Map
inline void AddV(int i,int val){
if (M.count(val)==0) v[i][++top[i]]=M[val]=M.size()+1;//新建一个编号
else v[i][++top[i]]=M[val];//沿用原来的编号
}

struct Query{
int l,r,id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){
return pos[A.l]<pos[B.l]||(pos[A.l]==pos[B.l]&&((pos[A.l]&1)?A.r<B.r:A.r>B.r));
}
int ans;
static int c[MAXN];
inline void Add(int x){
for (register int i=1;i<=top[x];++i){
ans=((long long)ans*inv[c[v[x][i]]+1])%MOD;
++c[v[x][i]],c[v[x][i]]%=MOD;
ans=((long long)ans*(c[v[x][i]]+1))%MOD;
}
}
inline void Del(int x){
for (register int i=1;i<=top[x];++i){
ans=((long long)ans*(inv[c[v[x][i]]+1]))%MOD;
--c[v[x][i]],(c[v[x][i]]+=MOD)%=MOD;
ans=((long long)ans*(c[v[x][i]]+1))%MOD;
}
}
static int Ans[MAXN];
int main(){
// freopen("yukideru.in","r",stdin);
// freopen("yukideru.out","w",stdout);
int n=read(),m=read();
Init(n);
for (register int i=1;i<=n;++i){
int a=read();
for (register int j=1;j<CNT;++j){//分开搞
sum[i][j]=sum[i-1][j];
while (a%prime[j]==0){
a/=prime[j],++sum[i][j];
}
}
if (a==1) continue;
for (register int j=CNT;j<=cnt;++j){
if (a==1) break;
while (a%prime[j]==0){
a/=prime[j],AddV(i,prime[j]);
}
}
if (a!=1) AddV(i,a);
}
for (register int i=1;i<=m;++i){
int l=read(),r=read();
q[i].l=l,q[i].r=r,q[i].id=i;
}
sort(q+1,q+1+m);
register int l=1,r=0;
ans=1ll;
for (register int i=1;i<=m;++i){
while (l>q[i].l) Add(--l);
while (r<q[i].r) Add(++r);
while (l<q[i].l) Del(l++);
while (r>q[i].r) Del(r--);
Ans[q[i].id]=ans;
for (register int j=1;j<CNT;++j){
Ans[q[i].id]=((long long)Ans[q[i].id]*(sum[r][j]-sum[l-1][j]+1))%MOD;//前缀和搞一下
}
}
for (register int i=1;i<=m;++i){
printf("%d\n",Ans[i]);
}
}

 评论