传送门
一道很有意思的题。
题意简述：给一个数列，多次询问区间的lcmlcmlcm，答案对1e9+71e9+71e9+7取模。
思路：首先考虑到一个区间的lcmlcmlcm就是其中所有出现过的素数的最大幂的乘积。
因此想到分开维护每一个素数。
然后由于pap^apa对答案原本是有pap^apa自己那么多贡献的，现在考虑将它拆分成p,p2,p3,...,pap,p^2,p^3,...,p^ap,p2,p3,...,pa共aaa个数，每个数有ppp的贡献，那么对于答案的总贡献还是pap^apa的 。
所以我们把每一个数都拆分。
设p=a1k1a2k2...amkmp=a_1^{k_1}a_2^{k_2}...a_m^{k_m}p=a1k1a2k2...amkm
那么我们将它拆成一段二元组(a1,a1),(a12,a1),...,(a1k1,a1),(a2,a2),(a22,a2),...,(a2k2,a2),...,(am,am),(am2,am),...,(amkm,am)(a_1,a_1),(a_1^2,a_1),...,(a_1^{k_1},a_1),(a_2,a_2),(a_2^2,a_2),...,(a_2^{k_2},a_2),...,(a_m,a_m),(a_m^2,a_m),...,(a_m^{k_m},a_m)(a1,a1),(a12,a1),...,(a1k1,a1),(a2,a2),(a22,a2),...,(a2k2,a2),...,(am,am),(am2,am),...,(amkm,am)
第一元表示数的值，第二元表示数的贡献。
然后现在相当于在重构之后的序列里询问区间中所有数的贡献之积，相同的数贡献只能算一次，这不就是HHHHHH的项链吗，于是用链表维护一下即可。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int mod=1e9+7,N=50005,M=8e5+5;
int n,m,tot,inv[N],L[M],R[M],pos[N],nxt[M],ans[N],bit[M];
struct Query{int l,r,id;}qry[N];
typedef pair<int,int> pii;
pii val[M];
inline bool cmp(const Query&a,const Query&b){return a.l<b.l;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int lowbit(int x){return x&-x;}
inline void update(int x,int v){for(ri i=x;i<=tot;i+=lowbit(i))bit[i]=mul(bit[i],v);}
inline int query(int x){int ret=1;for(ri i=x;i;i-=lowbit(i))ret=mul(ret,bit[i]);return ret;}
int main(){
n=read(),m=read(),inv[1]=1;
for(ri i=2;i<=50000;++i)inv[i]=mul(inv[mod%i],mod-mod/i);
for(ri i=1,x,tmp,lim;i<=n;++i){
x=read();
if(x==1)continue;
lim=sqrt(x),L[i]=tot+1;
for(ri j=2;j<=lim;++j){
if(x==x/j*j){
tmp=j;
while(x==x/j*j)x/=j,val[++tot]=pii(tmp,j),tmp*=j;
}
}
if(x^1)val[++tot]=pii(x,x);
R[i]=tot;
}
fill(bit+1,bit+tot+1,1);
for(ri i=1;i<=tot;++i){
if(pos[val[i].fi])nxt[pos[val[i].fi]]=i;
else update(i,val[i].se);
pos[val[i].fi]=i;
}
for(ri i=1;i<=m;++i)qry[i].l=L[read()],qry[i].r=R[read()],qry[i].id=i;
sort(qry+1,qry+m+1,cmp);
for(ri i=1,j=0;i<=tot;++i){
while(qry[j+1].l==i)++j,ans[qry[j].id]=query(qry[j].r);
update(i,inv[val[i].se]);
if(nxt[i])update(nxt[i],val[nxt[i]].se);
}
for(ri i=1;i<=m;++i)cout<<ans[i]<<'\n';
return 0;
}