思路大概是根号分治+预处理/莫队

提交记录

代码：

//g++ a.cpp -o a -g -std=c++14 -O0 -Wall -fsanitize=undefined
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<chrono>
#define LL long long
using namespace std;
namespace rdin{
	const int maxr=1e6+10;char buf[maxr],*l,*r;
	inline char gtc(){if(l==r){r=(l=buf)+fread(buf,1,maxr,stdin);}return l==r?EOF:*l++;}
	inline int qd(){int rt=0;char c=gtc();while(c<'0'||c>'9'){c=gtc();}while('0'<=c&&c<='9'){rt=(rt<<3)+(rt<<1)+(c^48),c=gtc();}return rt;}
}
using rdin::qd;
const int maxn=1e5+10,_maxn=1e5,sqmaxn=330,_sqmaxn=320,sqmo=512,mod=998244353;
int N,M,a[maxn],tn[maxn];LL ans[maxn],tnpi=1;vector<LL>mi[maxn],nmi[maxn];
struct node{int t,v,num;};vector<node>fac[maxn],pf[maxn];
inline bool cmp(const node &x,const node &y){return x.v==y.v?x.num<y.num:x.v<y.v;}
struct nodeq{int id,l,r;}q[maxn];
inline bool cmp2(const nodeq &x,const nodeq &y){return x.l/sqmo==y.l/sqmo?(x.r<y.r)^((x.l/sqmo)&1):x.l<y.l;}
inline LL qsm(LL x,LL y){LL rt=1;for(;y;y>>=1,x=x*x%mod){if(y&1){rt=rt*x%mod;}}return rt;}
inline LL getmi(int x,int t){
	for(int i=t-mi[x].size();i>=0;i--)  mi[x].emplace_back(mi[x].back()*mi[x].back()%mod);
	return mi[x][t];
}
inline LL getnmi(int x,int t){
	for(int i=t-nmi[x].size();i>=0;i--)  nmi[x].emplace_back(nmi[x].back()*nmi[x].back()%mod);
	return nmi[x][t];
}
inline LL dgetmi(int x,int t){return getmi(x,t)*nmi[x][0]%mod;}
inline LL dgetnmi(int x,int t){return getnmi(x,t)*mi[x][0]%mod;}
inline void upd(int x,int t){
	if(fac[x].empty())  return;
	x=fac[x].back().v;if(x<=_sqmaxn)  return;
//	(tnpi*=dgetnmi(x,tn[x]))%=mod;
//	(tnpi*=dgetmi(x,tn[x]+=t))%=mod;//x^(2^w-1)  =>  x^(2^w'-1) == * x^(2^w-2^w')
	(tnpi*=getnmi(x,tn[x])*getmi(x,tn[x]+t)%mod)%=mod;tn[x]+=t;
}
int stime(){return chrono::steady_clock::now().time_since_epoch().count()/1000;}
int main(){
//	freopen("in.txt","r",stdin);//int t0=stime();
	for(int i=1;i<=_maxn;i++)  mi[i].emplace_back(i),nmi[i].emplace_back(qsm(i,mod-2));
	for(int i=2;i<=_maxn;i++)  if(fac[i].empty())  for(int j=i;j<=_maxn;j+=i)  for(int x=j,t=1;x%i==0;x/=i,t++)  fac[j].push_back({1,i,t});
	N=qd(),M=qd();for(int i=1;i<=M;i++)  ans[i]=1;
//	printf("%d us\n",stime()-t0);t0=stime();
	for(int i=1;i<=N;i++){
		int x=a[i]=qd();
		for(auto t1=pf[i-1].begin(),t2=fac[x].begin();;){
			int nd1=t1==pf[i-1].end(),nd2=t2==fac[x].end()||t2->v>_sqmaxn;if(nd1&&nd2)  break;
			if(!nd1&&(nd2||cmp(*t1,*t2)))  pf[i].emplace_back(*t1),t1++;
			else if(!nd2&&(nd1||cmp(*t2,*t1)))  pf[i].emplace_back(*t2),t2++;
			else pf[i].push_back({t1->t+t2->t,t1->v,t1->num}),t1++,t2++;
		}
	}
//	printf("%d us\n",stime()-t0);t0=stime();//int tsum=0;
	for(int i=1;i<=M;i++){
		int l=qd(),r=qd();q[i]={i,l,r};//tsum+=pf[r].size()+pf[l-1].size();//if(i%64==0)  printf("%d:siz=%d\n",i,pf[r].size()+pf[l-1].size());
		for(auto t1=pf[l-1].begin(),t2=pf[r].begin();;){
			int nd1=t1==pf[l-1].end(),nd2=t2==pf[r].end();if(nd1&&nd2)  break;
			if(!nd1&&!nd2&&!cmp(*t1,*t2)&&!cmp(*t2,*t1))  (ans[i]*=dgetmi(t1->v,t2->t-t1->t))%=mod,t1++,t2++;
			else if(nd1||cmp(*t2,*t1))  (ans[i]*=dgetmi(t2->v,t2->t))%=mod,t2++;
			else abort();
		}
	}
//	printf("tsum=%d\n",tsum);
//	printf("%d us\n",stime()-t0);t0=stime();
	sort(q+1,q+M+1,cmp2);
	for(int i=1,tl=1,tr=0;i<=M;i++){
		int l=q[i].l,r=q[i].r;
		while(l<tl)  upd(a[--tl],1);
		while(tr<r)  upd(a[++tr],1);
		while(l>tl)  upd(a[tl++],-1);
		while(tr>r)  upd(a[tr--],-1);
		(ans[q[i].id]*=tnpi)%=mod;
	}
//	printf("%d us\n",stime()-t0);t0=stime();
	for(int i=1;i<=M;i++)  printf("%lld\n",ans[i]);
	return 0;
}