牛客練習賽9 F：珂朵莉的約數

​​題目傳送門​​ 參考部落格：牛客練習賽9 F - 珂朵莉的約數

我和該部落客一樣的地方：寫莫隊的時候發現了曾經沒有注意到的事情，就是要先進行add，然後進行delete。尴尬。。。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=100000+100;
const int primax=1000000+100;
const ll mod=1000000007;

int prime[primax],invprime[primax],tot,mi[primax];
bool isprime[primax];
int inv[primax<<1];
int number[primax];
int b[maxn]; //儲存超過1000的素因子 

int node[maxn][200];
int n,m;

struct Mo{
  
  int l,r;
  int id;
}mo[maxn];
int R[maxn];
bool cmp(Mo a,Mo b){
  
  return R[a.l]==R[b.l]?a.r<b.r:R[a.l]<R[b.l];
}

ll key;
ll Ans[maxn];

void init(){
  
  inv[0]=inv[1]=1;
  for(int i=2;i<(primax<<1);i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
  for(int i=0;i<primax;i++) isprime[i]=true;
  isprime[0]=isprime[1]=false;
  tot=0;
  for(int i=2;i<primax;i++){
    
    if(isprime[i]) invprime[i]=tot,prime[tot++]=i,mi[i]=i;
    for(int j=0;j<tot && i*prime[j]<primax;j++){
      
      isprime[i*prime[j]]=false;
      mi[i*prime[j]]=mi[i];
      if(!(i%prime[j])) break;
    }
  }
}

inline void kaven(int pri,int v){
  
  if(pri==0) return ;
  key=key*inv[number[pri]+1]%mod;
  number[pri]+=v;
  key=key*(number[pri]+1)%mod;
}

int main(){
  
  init();
  scanf("%d%d",&n,&m); 
  int size=sqrt(1.0*n);
  for(int i=1;i<=n;i++) R[i]=i/size;
  for(int i=1;i<=n;i++){
    
    int tmp;
    scanf("%d",&tmp);
    if(mi[tmp]>1000) b[i]=mi[tmp],tmp/=mi[tmp];
    while(tmp>1){
      
      int t=mi[tmp];
      int c=0;
      while(tmp%t==0) c++,tmp/=t;
      node[i][invprime[t]]=c;
    }
  }
  for(int i=2;i<=n;i++){
    
    for(int j=0;j<200;j++) node[i][j]+=node[i-1][j];
  }
  for(int i=1;i<=m;i++){
    
      scanf("%d%d",&mo[i].l,&mo[i].r);
    mo[i].id=i;
  }
  sort(mo+1,mo+1+m,cmp);
  int l=1,r=0;
  key=1;
  for(int i=1;i<=m;i++){
    
    while(l>mo[i].l) kaven(b[l-1],1),l--;
    while(r<mo[i].r) kaven(b[r+1],1),r++;
    while(r>mo[i].r) kaven(b[r],-1),r--;
    while(l<mo[i].l) kaven(b[l],-1),l++;
    
    ll tmp=1;
    for(int j=0;j<200;j++){
      
      ll Add=1+node[mo[i].r][j]-node[mo[i].l-1][j];
      tmp=tmp*Add%mod;
    }
    Ans[mo[i].id]=key*tmp%mod;
  }
  for(int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
}