「Codeforces 594D」REQ

Description

题目链接:Codeforces 594D

今天的数学课上,老师告诉 Vovochka 正整数的欧拉函数 $\varphi(n)​$ 是计算小于等于 $n​$ 且与 $n​$ 互质的正整数的函数,$1​$ 和任意正整数互质所以 $\varphi(1)=1​$。

现在老师给了 Vovochka 一个数列 $a_1,a_2,\dots,a_n​$,要求回答 $q​$ 个询问 $l_i,r_i​$,计算 $\varphi\left(\prod_{i=l}^r a_i\right)​$ 的值,答案对 $10^9 + 7​$ 取模。这个问题对二年级学生来说太难了,所以你决定帮助 Vovochka。

数据范围:$1\le n,q\le 2\times 10^5​$,$1\le a_i\le 10^6​$


Solution

由于只有询问操作,因此我们首先想到离线后用莫队解决。但是莫队的复杂度为 $O(q\sqrt n\log a_i)$(其中 $\log a_i$ 指每个数的本质不同的质因子个数),显然无法通过本题(我卡了半个小时常数还是 $\text{TLE}$ 出题人毒瘤)。

还是考虑离线,我们将询问按照右端点排序,维护一个右指针,将每个 $a_i​$ 逐个加入。用树状数组维护每个位置对答案的贡献。

我们考虑 $a_i​$ 的其中一个质因子 $p​$(其他的质因子同理)。由于我们把询问按照右端点排序了,而每个质因子只能对答案有一次贡献,那么我们把 $p​$ 的贡献放到区间 $[1,i]​$ 的最右边,即进行操作 $add(i,p-1)​$ 和 $add(i,p^{-1})​$。如果 $p​$ 已经出现过了,那么我们需要防止区间左端点左侧产生贡献,维护一个 $lst[i]​$ 表示 $i​$ 这个质因子上次出现的位置,将 $lst[p]​$ 位置的贡献消去即可。

对于如何快速分解每个数的质因子,我们可以根据线性筛的本质:每个数只会被其最小质因子筛去,在筛的过程中直接记录每个数的最小质因子即可!

时间复杂度:$O((n+q)\log n\log a_i)$


Code

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
#include <cstdio>
#include <algorithm>

const int N=2e5+5,M=1e6+5;
const int mod=1e9+7;
int n,m,tot,a[N],b[N],p[M/10],f[M],pre[N],lst[M],ans[N];
bool flg[M];

struct Data {
int l,r,id;
bool operator < (const Data &rhs) const {
return r<rhs.r;
}
} q[N];

void sieve(int n) {
for(int i=2;i<=n;++i) {
if(!flg[i]) p[++tot]=i,f[i]=i;
for(int j=1;j<=tot&&i*p[j]<=n;++j) {
flg[i*p[j]]=1,f[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}
int pow(int x,int p) {
int ret=1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ret=1LL*ret*x%mod;
return ret;
}
int inv(int x) {
return pow(x,mod-2);
}
void add(int x,int val) {
for(;x<=n;x+=x&-x) b[x]=1LL*b[x]*val%mod;
}
int query(int x) {
int ret=1;
for(;x;x^=x&-x) ret=1LL*ret*b[x]%mod;
return ret;
}
void update(int i) {
for(int x=a[i],p=f[x];x>1;p=f[x]) {
add(i,p-1),add(i,inv(p));
if(lst[p]) add(lst[p],inv(p-1)),add(lst[p],p);
lst[p]=i;
while(x%p==0) x/=p;
}
}
int main() {
sieve(M-5);
scanf("%d",&n);
pre[0]=1;
for(int i=1;i<=n;++i) scanf("%d",&a[i]),pre[i]=1LL*pre[i-1]*a[i]%mod;
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
std::sort(q+1,q+m+1);
for(int i=0;i<=n;++i) b[i]=1;
for(int i=1,j=0;i<=m;++i) {
int x=q[i].l,y=q[i].r;
while(j<y) update(++j);
ans[q[i].id]=1LL*pre[y]*inv(pre[x-1])%mod*query(y)%mod*inv(query(x-1))%mod;
}
for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}
0%