C++ 解法, 执行用时: 635ms, 内存消耗: 52216K, 提交时间: 2022-06-11 00:06:03

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e4+9,M=2299;
const LL mod=1e9+7;
int n,Q,cnt,m;
int a[N],p[N],q[N],pri[M],vis[N],st[49][N][19],nid[N];
set<int>pm[N];
void Prime()
{
	for(int i=2;i<=2e4;i++)
	{
		if(!vis[i]) pri[++cnt]=vis[i]=i,nid[i]=cnt;
		for(int j=1;j<=cnt;j++)
		{
			if(pri[j]>vis[i]||pri[j]*i>2e4) break;
			vis[pri[j]*i]=pri[j];
		}
	}
}
LL ksm(LL x,LL y)
{
	LL res=1;
	while(y)
	{
		if(y&1) res=res*x%mod;
		x=x*x%mod; y>>=1;
	}
	return res;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	Prime();
	m=sqrt(20000);
	cin>>n>>Q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		p[i]=q[i]=i;
		int x=a[i];
		for(int j=1;j<=cnt&&pri[j]<=m;j++)
		{
			int tot=0;
			while(x%pri[j]==0) tot++,x/=pri[j];
			st[j][i][0]=tot;
		}
		if(x>1) pm[x].insert(i);
	}
	for(int k=1;k<=cnt&&pri[k]<=m;k++)
		for(int j=1;j<=17;j++)
			for(int i=1;i+(1<<j)-1<=n;i++)
				st[k][i][j]=max(st[k][i][j-1],st[k][i+(1<<(j-1))][j-1]);
	while(Q--)
	{
		int l,r,k,nl=n+1,nr=0;
		cin>>l>>r;
		for(int i=l;i<=r;i++)
			nl=min(nl,p[i]),nr=max(nr,q[i]);
		LL ans=1;
		for(k=1;k<=cnt&&pri[k]<=m;k++)
		{
			int tl=nl,tot=0;
			for(int j=17;j>=0;j--)
				if(tl+(1<<j)-1<=nr)
					tot=max(tot,st[k][tl][j]),tl+=(1<<j);
			ans=ans*ksm(pri[k],tot)%mod;
		}
		for(;k<=cnt;k++)
		{
			if(pm[pri[k]].empty()) continue;
			auto it=pm[pri[k]].lower_bound(nl);
			if(it!=pm[pri[k]].end()&&(*it)<=nr) ans=ans*pri[k]%mod;
		}
		cout<<ans<<"\n";
		for(int i=l;i<=r;i++)
			p[i]=nl,q[i]=nr;
	}
	return 0;
}