- 给定了一个长度为\(n\)的序列。
- \(q\)次询问，每次给定一个区间，求区间内有多少对\(i,j\)满足\(a_i\)是\(a_j\)的倍数（\(i,j\)可以相同）。
- \(n,m,a_i\le5\times10^5\)
莫队二次离线
可以看看模板题：【洛谷4887】【模板】莫队二次离线。
不过个人感觉莫队二次离线的核心就是把指针的移动再次离线，而不同的题目在离线之后的操作还是千差万别，因此模板题似乎也没啥用。
对于这道题，这仅仅是基础中的基础，关键还是之后的操作。
设阈值分别处理
考虑我们设出一个分界值\(SN\)。
要给一个数的因数打标记，直接暴力\(\sqrt{a_i}\)枚举每个因数即可。
要给一个数的倍数打标记，如果它超过\(SN\)直接暴力，否则我们给这个因子打上另一种标记。
接下来处理某个前缀上二次离线后的询问，先枚举每个数统计标记和，然后枚举每个\(SN\)内的因子加上它的标记乘上区间内含这个因子的数的个数（这可以事先对每个因子前缀和预处理）。
注意，这里一个很妙的技巧，就是二次离线之后询问的个数仍然是\(O(m)\)级别的，因此我们依旧可以\(O(SN)\)枚举每个因子去处理每一个询问。
这样看起来很正确，但实际上会被卡内存。
因此我们想到去枚举每个小于等于\(SN\)的因数分别搞，这样就不用开\(SN\)个前缀和数组了。
但这样又会\(TLE\)，因此我们考虑内存并没有卡得这么夸张，实际上还是可以绑一些约数一起跑的，也就是说实际上只要把小于等于\(SN\)的因数拆成若*分分别搞即可。
具体实现中注意细节，这里相同的两个数\(a_i,a_j\)会计算两次，而相同的\(a_i,a_i\)却只计算一次。方便起见可以先让\(a_i,a_i\)计算两次，最后再给答案减去区间长度。
代码：\(O(n\sqrt n)\)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500000
#define SN 128
#define P 32
#define LL long long
using namespace std;
int n,m,a[N+5],sz,w[N+5],s[N+5][P];LL g[N+5],ans[N+5];
struct Q {int p,l,r;I bool operator < (Con Q& o) Con {return w[l]^w[o.l]?l<o.l:(w[l]&1?r<o.r:r>o.r);}}q[N+5];//询问
struct Q2 {int p,l,r,op;I Q2(CI i=0,CI a=0,CI b=0,CI c=0):p(i),l(a),r(b),op(c){}};vector<Q2> v[N+5];//二次离线的询问
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int main()
{
RI i,j;for(read(n,m),sz=sqrt(n),i=1;i<=n;++i) read(a[i]),w[i]=(i-1)/sz+1;
for(i=1;i<=m;++i) read(q[i].l,q[i].r),q[i].p=i;
RI L=1,R=0;for(sort(q+1,q+m+1),i=1;i<=m;++i)//莫队
R<q[i].r&&(v[L-1].push_back(Q2(q[i].p,R+1,q[i].r,-1)),R=q[i].r),
L>q[i].l&&(v[R].push_back(Q2(q[i].p,q[i].l,L-1,1)),L=q[i].l),
R>q[i].r&&(v[L-1].push_back(Q2(q[i].p,q[i].r+1,R,1)),R=q[i].r),
L<q[i].l&&(v[R].push_back(Q2(q[i].p,L,q[i].l-1,-1)),L=q[i].l);
RI p,vs;for(i=1;i<=N;++i) w[i]=0;for(i=1;i<=n;++i)//处理大于SN的因数的贡献和倍数的贡献
{
if(g[i]=w[a[i]],a[i]>SN) for(j=a[i];j<=N;j+=a[i]) ++w[j];//g记录当前数的标记；给大于SN的数的倍数打标记
for(j=1;j*j<=a[i];++j) !(a[i]%j)&&(++w[j],j^(a[i]/j)&&++w[a[i]/j]);//给约数打标记
for(j=0,vs=v[i].size();j^vs;++j) for(p=v[i][j].l;p<=v[i][j].r;++p) ans[v[i][j].p]+=v[i][j].op*w[a[p]];//枚举询问中的每个点暴力求标记和
}
int c[P];for(RI o=1;o<=SN;o+=P)//枚举P个小于等于SN的因数一起搞
{
for(i=1;i<=n;++i) for(p=0;p^P;++p) s[i][p]=s[i-1][p]+!(a[i]%(o+p));//预处理前缀和
for(p=0;p^P;++p) c[p]=0;for(i=1;i<=n;++i)
{
for(p=0;p^P;++p) !(a[i]%(o+p))&&(g[i]+=c[p]);for(p=0;p^P;++p) a[i]==o+p&&++c[p];//g加上因数的标记；给这些因数打标记
for(j=0,vs=v[i].size();j^vs;++j) for(p=0;p^P;++p)//枚举询问
ans[v[i][j].p]+=1LL*v[i][j].op*c[p]*(s[v[i][j].r][p]-s[v[i][j].l-1][p]);//区间询问更新贡献
}
}
for(i=1;i<=n;++i) g[i]+=g[i-1];//前缀和
for(L=1,R=0,i=1;i<=m;++i) ans[q[i].p]+=ans[q[i-1].p]+g[q[i].l-1]-g[L-1]+g[q[i].r]-g[R]+2*(q[i].r-R),L=q[i].l,R=q[i].r;//记得给求出的答案做前缀和
for(i=1;i<=m;++i) ans[q[i].p]-=q[i].r-q[i].l+1;for(i=1;i<=m;++i) writeln(ans[i]);return clear(),0;//每个答案减去区间长度
}