长度为N的正整数序列S，有Q次询问，每次询问一段区间内所有数的lcm(即最小公倍数)。由于答案可能很大，输出答案Mod 10^9 + 7。
例如：2 3 4 5，询问[1,3]区间的最小公倍数为2 3 4的最小公倍数 = 12。
Input
第1行：两个整数，N, Q，中间用空格分隔，N为数列长度，Q为询问数量。(2 <= N, Q <= 50000)
第2 - N + 1行：每行1个整数，对应数列中的元素(1 <= S[i] <= 50000)
第N + 2 - N + Q + 1行：每行2个数，l, r，表示询问下标i在[l, r]范围内的S[i]的最小公倍数。(1 <= l <= r <= N)
Output
输出共Q行，对应询问区间的最小公倍数Mod 10^9 + 7。
Input示例
3 3
123
234
345
1 2
2 3
1 3
Output示例
9594
26910
1103310 离线莫队，为了避免删数需要每次从当前块的终点跑到询问的左区间加数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 50001
using namespace std;
int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int MOD=1e9+;
const int K=;
struct na{
int l,r,k,p;
}Q[MN];
int n,m,A,p[MN],num=,bo[MN],_p[MN][],a[MN][],Nu[MN],l,r,mmh[MN],L,R,t[MN],_t[MN],MMH,_MMH;
inline bool cmp(na a,na b){return a.k==b.k?a.r<b.r:a.k<b.k;}
inline int mi(int a,int b){
int mmh=;
while (b){
if (b&) mmh=1LL*mmh*a%MOD;
b>>=;a=1LL*a*a%MOD;
}
return mmh;
}
inline void in(int x){for (register int i=;i<=Nu[x];i++) if (a[x][i]>t[_p[x][i]]) MMH=1LL*MMH*mi(p[_p[x][i]],a[x][i]-t[_p[x][i]])%MOD,t[_p[x][i]]=a[x][i];}
inline void work(int R,int x){
register int i,j;_MMH=MMH;
for (i=Q[x].l;i<=R;i++)
for (j=;j<=Nu[i];j++) if (a[i][j]>(_t[_p[i][j]]=_t[_p[i][j]]==?t[_p[i][j]]:_t[_p[i][j]])) _MMH=1LL*_MMH*mi(p[_p[i][j]],a[i][j]-_t[_p[i][j]])%MOD,_t[_p[i][j]]=a[i][j];
mmh[Q[x].p]=_MMH;
for (i=Q[x].l;i<=R;i++)
for (j=;j<=Nu[i];j++) _t[_p[i][j]]=;
}
int main(){
register int i,j;
for (i=;i<MN;i++){
if (!bo[i]) p[++num]=i,bo[i]=num;
for (j=;j<=num&&i*p[j]<MN;j++){
bo[i*p[j]]=j;
if (i%p[j]==) break;
}
}
n=read();m=read();
for (i=;i<=n;i++){
A=read();
while (A>){
if (bo[A]!=_p[i][Nu[i]]) _p[i][++Nu[i]]=bo[A];a[i][Nu[i]]++;A/=p[bo[A]];
}
}
for (i=;i<=m;i++)
Q[i].l=read(),Q[i].r=read(),Q[i].k=(Q[i].l-)/K,Q[i].p=i;
sort(Q+,Q++m,cmp);
r=;
for (i=;i<=(n-)/K;i++){
R=i*K+K;memset(t,,sizeof(t));MMH=;
while (Q[r].k==i&&r<=m){
if ((Q[r].r-)/K==i) work(Q[r].r,r);else{
while(R<=Q[r].r) in(R),R++;
work(i*K+K-,r);
}
r++;
}
}
for (i=;i<=m;i++) printf("%d\n",mmh[i]);
}