题面

题解

维包一生推

首先请确保您会

那么我们现在的问题就是怎么转移了，对于\(i\)和前缀\([1,r]\)的贡献，我们拆成\(b_i\)和\(c_i\)两部分，其中\(b_i\)表示\(i\)的因数个数，\(c_i\)表示\(i\)的倍数个数

\(c_i\)非常好处理，插入\(a_i\)的时候直接暴力枚举它的所有因子\(d\)，并令\(c_d++\)就好了，预处理之后复杂度上界是\(O(\sqrt{n})\)的

然而\(b_i\)就显得非常辣手……因为如果\(b_i\)很小的时候我们暴力枚举倍数复杂度是\(O(n)\)的……

那么我们就用老办法，设阈值\(s\)，如果\(a_i>s\)暴力枚举倍数并加上\(b_i\)，否则我们就需要用到一些奇技淫巧

我们记录一个\(s\)位的状态\(p\)，其中第\(k\)位为\(1\)当且仅当\(k|a_i\)，我们开一个大小为\(2^s\)的数组，那么这里的答案需要加上\(p_{ss(a_i)}\)，其中\(ss(a_i)\)表示\(a_i\)的这\(s\)个因子的存在情况。插入\(a_i\)的时候，只要把\(a_i\)是\(s\)的子集对应的\(p_s++\)就行了

暴力枚举倍数的复杂度为\(O({n\over s})\)，所以我们设\(s=32\)，然而这样的话\(2^s\)的空间显然会爆炸，那么我们把它拆成\(4\)个\(8\)位的状态就行了

然后没有然后了，具体可以看代码

//minamoto#include
    
     #define R register#define pb push_back#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;typedef long long ll;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'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 K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}void print(R ll x){    if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++K]=z[Z],--Z);sr[++K]='\n';}const int N=2e5+5;int a[N],bl[N],c[N],b[N],n,m,blo;ll s1[N],s2[N],ret[N],ans[N],res;struct node{    int l,r,id;    inline node(){}    inline node(R int li,R int ri,R int ii):l(li),r(ri),id(ii){}    inline bool operator <(const node &b)const{return bl[l]==bl[b.l]?r
         
          
           
            Q[N];typedef vector
            
             ::iterator IT;vector
             
              vec[N];int ss[N],r1[N],r2[N],r3[N],r4[N];inline void init(int n=1e5){ fp(i,1,n)for(R int j=i;j<=n;j+=i)vec[j].pb(i); fp(i,1,n)fp(j,1,32)if(i%j==0)ss[i]|=(1<
              
               >(x-1)&1); else if(x<=16)fp(i,0,255)r2[i]+=(i>>(x-9)&1); else if(x<=24)fp(i,0,255)r3[i]+=(i>>(x-17)&1); else fp(i,0,255)r4[i]+=(i>>(x-25)&1); }else for(R int i=x;i<=100000;i+=x)++b[i];}inline int calc(R int x){ x=ss[x]; return r1[x&255]+r2[x>>8&255]+r3[x>>16&255]+r4[x>>24&255];}inline int sum(R int x){return c[x]+b[x]+calc(x);}int main(){// freopen("testdata.in","r",stdin); n=read(),m=read(),blo=500,init(); fp(i,1,n)a[i]=read(),bl[i]=(i-1)/blo+1; fp(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i; sort(q+1,q+1+m); for(R int i=1,l=q[1].r+1,r=q[1].r;i<=m;++i){ if(l
               
                <<1)); else if(l>q[i].l)Q[r].pb(node(q[i].l,l-1,q[i].id<<1)); l=q[i].l; if(r
                
                 <<1|1)); else if(r>q[i].r)Q[l-1].pb(node(q[i].r+1,r,q[i].id<<1|1)); r=q[i].r; } fp(i,1,n){ s1[i]=s1[i-1]+sum(a[i]); fp(k,0,vec[a[i]].size()-1)++c[vec[a[i]][k]]; ins(a[i]); s2[i]=s2[i-1]+sum(a[i]); for(IT it=Q[i].begin();it!=Q[i].end();++it) fp(k,it->l,it->r)ret[it->id]+=sum(a[k]); } for(R int i=1,l=q[1].r+1,r=q[1].r;i<=m;++i){ if(l
                 
                  <<1]-s2[q[i].l-1]+s2[l-1]; else if(l>q[i].l)res+=ret[q[i].id<<1]-s2[l-1]+s2[q[i].l-1]; l=q[i].l; if(r
                  
                   <<1|1]; else if(r>q[i].r)res-=s1[r]-s1[q[i].r]-ret[q[i].id<<1|1]; r=q[i].r,ans[q[i].id]=res+r-l+1; } fp(i,1,m)print(ans[i]); return Ot(),0;}