TLE#2,3,4，其中 #2 是 $3.10s$ 左右，#3,4 都是 $3.20s$ 之外

话说这题以前好像时限是 $5s$ 啊。。为啥要调成 $3s$

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline char nc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	char ch=nc();
	int sum=0;
	while(!(ch>='0'&&ch<='9'))ch=nc();
	while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
	return sum;
}
inline void out(ll a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

const int MN=5e5+5;

int n,m,a[MN];

struct Query{int l,r,id;ll ans;}q[MN];
int bl[MN],len,pre[MN],M,cnt[MN],sum[MN],B;
ll ans[MN];

vector<int>d[MN];
bool vis[MN];

struct Node{
	int l,r,id;
	Node(int L,int R,int I):l(L),r(R),id(I){}
	Node(){}
};
vector<Node>vec[MN];

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif	

	n=read(),m=read();len=1000;
	for(int i=1;i<=n;i++){
		a[i]=read(),M=max(M,a[i]);
		if(vis[a[i]])continue;
		for(int x=1;x*x<=a[i];x++){
			if(a[i]%x==0){
				d[a[i]].emplace_back(x);
				if(x*x!=a[i])d[a[i]].emplace_back(a[i]/x);
			}
		}
		vis[a[i]]=1;
	}
	B=25;

	for(int i=1;i<=n;i++){
		pre[i]+=sum[a[i]];
		for(int x:d[a[i]])sum[x]++,pre[i]+=cnt[x];
		cnt[a[i]]++;pre[i]+=pre[i-1];
		// cout<<pre[i]-pre[i-1]<<' ';
	}//puts("");
	for(int i=1;i<=n;i++)bl[i]=(i-1)/len+1;

	for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1,[](const Query &x,const Query &y){
		if(bl[x.l]!=bl[y.l])return bl[x.l]<bl[y.l];
		if(bl[x.l]&1)return x.r<y.r;
		else return x.r>y.r;
	});

	int l=1,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		// cout<<l<<" "<<r<<" -> "<<ql<<" "<<qr<<endl;
		if(l>ql)vec[r].emplace_back(Node(ql,l-1,i)),q[i].ans-=(pre[l-1]-pre[ql-1]+l-ql),l=ql; //+ [ql,l-1]->[l,r]
		if(r<qr)vec[l-1].emplace_back(Node(r+1,qr,-i)),q[i].ans+=(pre[qr]-pre[r]+qr-r),r=qr; //+ [r+1,qr]->[l,r]
		if(l<ql)vec[r].emplace_back(Node(l,ql-1,-i)),q[i].ans+=(pre[ql-1]-pre[l-1]+ql-l),l=ql; //- [l,ql-1]->[l,r]
		if(r>qr)vec[l-1].emplace_back(Node(qr+1,r,i)),q[i].ans-=(pre[r]-pre[qr]+r-qr),r=qr; //- [qr+1,r]->[l,r]
	}

	//solve big
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++){
		for(int x:d[a[i]])sum[x]++;
		if(a[i]>B)for(int x=a[i];x<=M;x+=a[i])sum[x]++;
		for(auto t:vec[i]){
			for(int x=t.l;x<=t.r;x++){
				if(t.id>0)q[t.id].ans+=1ll*sum[a[x]];
				else q[-t.id].ans-=1ll*sum[a[x]];
			}
		}
	}

	//solve small
	memset(sum,0,sizeof(sum));
	for(int x=1;x<=B;x++){
		if(!vis[x])continue;
		int num=0;
		for(int i=1;i<=n;i++)sum[i]=(a[i]%x==0)+sum[i-1];
		for(int i=1;i<=n;i++){
			num+=(a[i]==x);
			for(auto t:vec[i]){
				if(t.id>0)q[t.id].ans+=(1ll*(sum[t.r]-sum[t.l-1]))*(1ll*num);
				else q[-t.id].ans-=(1ll*(sum[t.r]-sum[t.l-1]))*(1ll*num);
			}
		}
	}

	for(int i=1;i<=m;i++)q[i].ans+=q[i-1].ans;
	for(int i=1;i<=m;i++)ans[q[i].id]=q[i].ans;
	for(int i=1;i<=m;i++)out(ans[i]),putchar('\n');

	return 0;
}