Link
莫队二次离线。
对于([l,r])与([1,i])的贡献，考虑对每个(xin[l,r])，单独计算(x)与([1,i])的贡献。
把贡献拆成(b,c)两部分，其中(b_x)表示([1,i])的中(a_x)的因数的个数，(c_x)表示([1,i])中(a_x)的倍数的个数。
(c)非常简单，插入(x)时时暴力枚举因子(d)然后令(c_d)加一。
对于(b)，插入(x)时若(x>sqrt n)就暴力枚举倍数(g)然后令(b_g)加一。
那么我们现在还需要计算的就是([1,i])中有多少个(<sqrt n)的(x)的因数。这个看上去很不好做。
我们尝试回退一步，不把询问区间([l,r])拆成单个的(x)，这样我们要做的就是求(ans=sumlimits_{p=1}^isumlimits_{q=l}^r[a_plesqrt nwedge a_p|a_q])。
这个东西一看就知道怎么拆了，(ans=sumlimits_{x=1}^{sqrt n}(sumlimits_{p=1}^i[a_p=x])(sumlimits_{q=l}^r[x|a_q]))。
那么我们预处理(x)在([1,i])中的出现次数(s_{x,i})，以及(x)的倍数在([1,i])中的出现次数(t_{x,i})即可(O(sqrt n))回答一个区间的询问。
时间复杂度和空间复杂度都是空间复杂度是(O(nsqrt n))。如果在最后一部分的计算中从小到大枚举(x)然后只计算(x)的贡献可以做到(O(n))空间。
另一种写法
先根号分治再莫队二次离线。
对于所有的({(i,j)|a_j|a_i})，我们将其分为两类：
(a_jle lim)：(ans_{l,r}=sumlimits_{x=1}^{lim}(sumlimits_{i=l}^r[a_i=x])(sumlimits_{i=l}^r[x|a_i]))，这东西怎么算上面已经讲过了。
(a_j>lim)：莫队二次离线。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<numeric>
#include<algorithm>
using std::sort;
using std::vector;
using i64=long long;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[13],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
void Put(char x){*oS++=x;if(oS==oT)Flush();}
int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
void write(i64 x){int top=0;if(!x)Put('0');while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put('
');}
}using IO::read;
const int N=500007;
int n,m,mx,lim,size,cnt,a[N];i64 f[N],g[N],del[N],ans[N];
struct query{int l,r,id;}q[N];struct node{int p,l,r,id,o;}b[N<<1];
std::vector<int>fac[N];
void get()
{
static i64 sum[N],val=1e18;
for(int i=1;i<=n;++i) sum[a[i]]+=n/a[i];
for(int i=mx;i;--i) sum[i]+=sum[i+1];
for(int i=1;i*i<=mx;++i) if(i*n*5+sum[i+1]<val) val=i*n*5+sum[i+1],lim=i;
}
void calc1()
{
static int t[N];
for(int i=1;i<=n;++i)
{
if(a[i]<=lim) continue;
for(int x:fac[a[i]]) g[i]+=t[x];
for(int j=a[i];j<=mx;j+=a[i]) g[i]+=t[j];
++t[a[i]],f[i]=g[i]+2;
}
std::partial_sum(f+1,f+n+1,f+1),std::partial_sum(g+1,g+n+1,g+1);
}
void calc2()
{
static int s[N],t[N];
for(int x=1;x<=lim;++x)
{
for(int i=1;i<=n;++i) s[i]=s[i-1]+!(a[i]%x),t[i]=t[i-1]+(a[i]==x);
for(int i=1;i<=m;++i) ans[q[i].id]+=1ll*(t[q[i].r]-t[q[i].l-1])*(s[q[i].r]-s[q[i].l-1]+1);
}
}
void calc3()
{
static int t[N],p;
for(p=1;p<=cnt&&!b[p].p;++p);
for(int i=1;i<=n;++i)
{
if(a[i]>lim)
{
for(int x:fac[a[i]]) ++t[x];
for(int j=a[i];j<=mx;j+=a[i]) ++t[j];
}
for(;p<=cnt&&b[p].p==i;++p) for(int j=b[p].l;j<=b[p].r;++j) del[b[p].id]+=b[p].o*t[a[j]];
}
}
void getans()
{
std::partial_sum(del+1,del+m+1,del+1);
for(int i=1;i<=m;++i) ans[q[i].id]+=del[i]-(q[i].r-q[i].l+1);
for(int i=1;i<=m;++i) IO::write(ans[i]);
IO::Flush();
}
int main()
{
n=read(),m=read(),size=n/sqrt(m+1)*1.5+1;
for(int i=1;i<=n;++i) mx=std::max(a[i]=read(),mx);
for(int i=1;i<=m;++i) q[i]={read(),read(),i};
get();
for(int i=lim+1;i<=mx;++i) for(int j=i;j<=mx;j+=i) fac[j].push_back(i);
std::sort(q+1,q+m+1,[](const query&a,const query&b){return a.l/size==b.l/size? ((a.l/size)&1? a.r>b.r:a.r<b.r):a.l/size<b.l/size;}),calc1(),calc2();
for(int i=1,l=q[1].r+1,r=q[1].r;i<=m;++i)
{
if(l>q[i].l) del[i]-=g[l-1]-g[q[i].l-1],b[++cnt]={r,q[i].l,l-1,i,1},l=q[i].l;
if(l<q[i].l) del[i]+=g[q[i].l-1]-g[l-1],b[++cnt]={r,l,q[i].l-1,i,-1},l=q[i].l;
if(r<q[i].r) del[i]+=f[q[i].r]-f[r],b[++cnt]={l-1,r+1,q[i].r,i,-1},r=q[i].r;
if(r>q[i].r) del[i]-=f[r]-f[q[i].r],b[++cnt]={l-1,q[i].r+1,r,i,1},r=q[i].r;
}
std::sort(b+1,b+cnt+1,[](const node&a,const node&b){return a.p<b.p;});
calc3(),getans();
}