显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=50010,mod=1e9+7;
int mul(int x,int y){return (ll)x*y%mod;}
int n,m,a[N],inv[N],p[N],cnt;
bool isp[N];
int prime[N][7],power[N][7],val[N][18],np[N],lg[N];
void init(){
inv[1]=1;
for (int i=2;i<N;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
static int mi[N];
isp[1]=1;
for (int i=2;i<N;i++)
if (!isp[i]){
p[++cnt]=i;
val[i][0]=1;
for (unsigned int now=i;now<N;now*=i)
val[i][++lg[i]]=now;
for (int j=i;j<N;j+=i){
isp[j]=1;
prime[j][np[j]]=i;
power[j][np[j]]=mi[j]=mi[j/i]+1;
np[j]++;
}
for (int j=i;j<N;j+=i) mi[j]=0;
}
}
int now,size,num[N][18],Max[N];
//Max[p]表示p的最大次数,num[p][i]表示p^i出现次数
void update(int p){
now=mul(now,inv[Max[p]]);
for (int i=lg[p];i>=0;i--)
if (num[p][i]){Max[p]=val[p][i];break;}
now=mul(now,Max[p]);
}
void push(int p,int cnt){
num[p][cnt]++;
update(p);
}
void push(int x){
size++;
for (int i=0;i<np[x];i++) push(prime[x][i],power[x][i]);
}
void del(int p,int cnt){
num[p][cnt]--;
update(p);
}
void del(int x){
size--;
for (int i=0;i<np[x];i++) del(prime[x][i],power[x][i]);
}
struct query{int l,r,id;}Q[N];
int block;
bool cmp(const query &x,const query &y){
return x.l/block==y.l/block?x.r<y.r:x.l<y.l;
}
int ans[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int GCD[N*4];
#define lc x<<1
#define rc x<<1|1
void build(int x,int l,int r){
if (l==r) return void(GCD[x]=a[l]);
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
GCD[x]=gcd(GCD[lc],GCD[rc]);
}
int getgcd(int x,int l,int r,int L,int R){
if (l>=L&&r<=R) return GCD[x];
int mid=(l+r)>>1,ans=0;
if (L<=mid) ans=gcd(getgcd(lc,l,mid,L,R),ans);
if (R>mid) ans=gcd(getgcd(rc,mid+1,r,L,R),ans);
return ans;
}
int main()
{
freopen("Keller_T233.in","r",stdin);
freopen("Keller_T233.out","w",stdout);
init();
scanf("%d%d",&n,&m);
block=sqrt(n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for (int i=1;i<=n;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
sort(Q+1,Q+m+1,cmp);
now=1;
for (int i=1;i<N;i++) num[i][0]=1e9,Max[i]=1;
int l=Q[1].l,r=l-1;
for (int i=1;i<=m;i++){
while (r<Q[i].r) push(a[++r]);
while (l>Q[i].l) push(a[--l]);
while (r>Q[i].r) del(a[r--]);
while (l<Q[i].l) del(a[l++]);
ans[Q[i].id]=mul(now,getgcd(1,1,n,l,r));
}
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
FoolMike