LuoguP5071 [Ynoi2015] 此时此刻的光辉
Description
题目链接：P5071
给定一个长为 n 的序列，有 m 次查询，每次查询一段区间的乘积的约数个数 bmod 19260817 的值。
1leq n,m leq 10^5,1leq a_i leq 10^9
Solution
乍看题目，不难想到一种很暴力的做法：先对每个数质因数分解，然后利用约数和定理直接莫队即可。
但一点开题解区发现都过不了，还要用pr&根号分治。
但是后来经过陈指导的提醒，直接敲了个暴力就跑过去了（
这里列举一些优化：
- 预处理线性求逆元。
- 筛素数不一定要筛到 sqrt{10^9}，可以适量调大点。
- 有信仰
Code
代码语言：javascript复制#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 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;
}
