lxl大毒瘤

首先一个数的因子个数就是这个数的每个质因子的次数+1的积，然后考虑把每个数分解质因子，用莫队维护，然后我交上去就0分了

如果是上面那样的话，我们每一次移动指针的时间复杂度是O(这个数的质因子个数)，再加上我人傻常数大，T很正常……

于是按照memset0的说法，可以预处理质因子的前缀和，简单来说就是对于小于\(\sqrt{mx}\)的所有质因子维护前缀和，直接统计，大于的暴力在莫队的时候更新。因为每个数大于\(\sqrt{mx}\)的质因子个数为\(O(1)\)，所以暴力更新的复杂度是\(O(1)\)的

然后我维护前缀和这里想岔了……死活没想明白怎么用前缀和更新答案……实际上就是用前缀和每一次暴力统计所有小于\(\sqrt{mx}\)的质因子个数，总共统计次数为\(O(q)\)，所以这一部分的时间复杂度为\(O(q\sqrt{mx})\)

然后加起来差不多是\(O(n\sqrt{n})\)

//minamoto#include
    
     #define R register#define IT vector
     
      ::iterator#define fp(i,a,b) for(R int i=a,I=b+1;i
      
       I;--i)#define go(u) for(IT it=v[u].begin();it!=v[u].end();++it)template
       
        inline bool cmax(T&a,const T&b){return a
        
         '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=1e5+5,P=19260817;struct node{    int v,cnt;    node(){}    node(R int v,R int cnt):v(v),cnt(cnt){}};vector
         
          v[N];map
          
           mp;map
           
            ::iterator it;int p[N],inv[P+5],cnt[N<<1],b[N],ans[N],rt[N],vis[N],sum[N][165],a[N];int m,lim,n,now=1,S,Q,cc,L=155,mx,l,r;struct query{ int l,r,id; inline bool operator <(const query &b)const{return rt[l]==rt[b.l]?rt[l]&1?r
            
             b.r:l
             
              second; ins(id,x,1); }}void add(int id){ go(id)now=1ll*now*inv[cnt[it->v]+1]%P,cnt[it->v]+=it->cnt,now=1ll*now*(cnt[it->v]+1)%P;}void del(int id){ go(id)now=1ll*now*inv[cnt[it->v]+1]%P,cnt[it->v]-=it->cnt,now=1ll*now*(cnt[it->v]+1)%P;}int main(){// freopen("testdata.in","r",stdin);// freopen("testdata.out","w",stdout); n=read(),Q=read(),S=sqrt(n);fp(i,1,n)a[i]=read(),cmax(mx,a[i]),rt[i]=(i-1)/S;init(sqrt(mx)); lim=m;fp(i,1,n){ fp(j,1,L)sum[i][j]=sum[i-1][j];solve(a[i],i); }inv[0]=inv[1]=1;fp(i,2,P-1)inv[i]=1ll*(P-P/i)*inv[P%i]%P; fp(i,1,Q)q[i].l=read(),q[i].r=read(),q[i].id=i; sort(q+1,q+1+Q);l=1,r=0; fp(i,1,Q){ while(l>q[i].l)add(--l);while(r
              
               q[i].r)del(r--); ans[q[i].id]=now;fp(j,1,L)ans[q[i].id]=1ll*ans[q[i].id]*(sum[r][j]-sum[l-1][j]+1)%P; }fp(i,1,Q)print(ans[i]);return Ot(),0;}