「Codeforces 594D」REQ

发表于 | | 阅读次数:
字数统计: 919 字

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%