LuoguP5071 [Ynoi2015] 此时此刻的光辉

(Updated: )
oi

Description

题目链接：P5071

给定一个长为 $n$ 的序列，有 $m$ 次查询，每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。

$1\leq n,m \leq 10^5,1\leq a_i \leq 10^9$

Solution

乍看题目，不难想到一种很暴力的做法：先对每个数质因数分解，然后利用约数和定理直接莫队即可。

但一点开题解区发现都过不了，还要用pr&根号分治。

但是后来经过陈指导的提醒，直接敲了个暴力就跑过去了（

这里列举一些优化：

  1. 预处理线性求逆元。
  2. 筛素数不一定要筛到 $\sqrt{10^9}$，可以适量调大点。
  3. 有信仰

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear(){fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x){x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void writeln(Ty x){W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,S=650,M=N/S+10,P=19260817;
int n,m,bl[N],X,p[71625],s[500000],c[N][12],tot,Inv[N*30+10],sz[N],g[N][12],Ans[N];
struct Que{int l,r,id;}q[N];
I bool cmp(Cn Que& x,Cn Que& y){return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;}
map<int,int> mp;
I void Get(){
    for(RI j,t,i=2;i<=71622;i++) for(!p[i]&&(p[++tot]=i,mp[i]=tot),j=1;j<=tot&&(t=i*p[j])<=71622;j++)
    if(p[t]=1,!(i%p[j])) break ;//线性筛质数
}
I void Init(CI x,RI v){
    for(RI i=1;i<=tot&&1LL*p[i]*p[i]<=v;i++) if(!(v%p[i])){
        g[x][++sz[x]]=i;W(v/=p[i],c[x][sz[x]]++,!(v%p[i]));//预处理每个数字质因数分解
    }if(v>1) !mp[v]&&(mp[v]=++tot),g[x][++sz[x]]=mp[v],c[x][sz[x]]=1;//注意大质数情况
}
I void U(CI x,CI v){
    for(RI i=1;i<=sz[x];i++) X=1LL*X*Inv[s[g[x][i]]+1]%P*((s[g[x][i]]+=v*c[x][i])+1)%P;
}
int main(){
    RI i,x,l,r;for(Get(),Inv[0]=Inv[1]=1,i=2;i<=30*N;i++) Inv[i]=P-1LL*P/i*Inv[P%i]%P;//线性求逆元
    for(read(n,m),i=1;i<=n;i++) read(x),Init(i,x),bl[i]=(i-1)/S+1;
    for(i=1;i<=m;i++) read(q[i].l,q[i].r),q[i].id=i;for(sort(q+1,q+m+1,cmp),l=1,r=0,X=1,i=1;i<=m;i++){
        W(r<q[i].r) U(++r,1);W(r>q[i].r) U(r--,-1);W(l>q[i].l) U(--l,1);W(l<q[i].l) U(l++,-1);Ans[q[i].id]=X;//莫队
    }for(i=1;i<=m;i++) writeln(Ans[i]);return clear(),0;
}