不知道为什么，一直T飞，照dX的代码和CICN的代码改了一下依然T飞。

这是什么/tuu卡常题……

#include "bits/stdc++.h"
using namespace std;
const int Len = 5e5 + 5;
#define getchar() (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<21,stdin),P1==P2)?EOF:*P1++)
char buf[1<<21],*P1=buf,*P2=buf,obuf[1<<24],*O=obuf;
inline int read(){
   int s=0;
   char ch=getchar();
   while(ch<'0'||ch>'9') ch=getchar();
   while(ch>='0'&&ch<='9') s=s*10+(ch^48),ch=getchar();
   return s;
}
void write(long long x) {
    if(x>9) write(x/10);
    *O++=x%10+'0';
}
int n,q,a[Len],maxa,pre[Len],lsh[Len],cnt,t,vt,block[Len],B[Len],b[Len],c[Len],L[Len],R[Len],dc[Len],d[Len],vs[Len * 20];
long long p1[Len],p2[Len];
long long Print[Len];
struct node
{
	int l,r,id;
	long long ans;
}Sec[Len];
bool cmp(node x,node y)
{
	if(block[x.l] == block[y.l]) return x.r < y.r;
	return block[x.l] < block[y.l];
}
struct Node
{
	int l,r,idx,op,i;
}ques[Len << 1];
int qcnt;
bool cmd(Node x,Node y){return x.i < y.i;}
int main()
{
	n = read() , q = read();t = 1000;
	for(int i = 1 ; i <= n ; ++ i)
	{
		lsh[i] = a[i] = read();
		maxa = max(maxa , a[i]);
		block[i] = (i - 1) / t + 1;
	}
	sort(lsh + 1 , lsh + 1 + n);
	for (int i = n ; i >= 1 ; i --) c[i] = c[i + 1] + lsh[n] / lsh[i];
	int idx = 1;
	long long minC = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1 ; i * i <= n ; ++ i) 
	{
		while(idx <= n && lsh[idx] < i) ++ idx;
		if (1LL * n * i / 2 + c[idx] < minC) 
		{
			vt = i;
			minC = 1LL * n * i / 2 + c[idx];
		}
	}
	for(int i = 1 ; i <= q ; ++ i)
	{
		Sec[i].l = read() , Sec[i].r = read();
		Sec[i].id = i;
	}
	sort(Sec + 1 , Sec + 1 + q , cmp);
	for(int i = 1 ; i <= maxa ; ++ i)
		for(int j = i ; j <= maxa ; j += i) ++ dc[j];
	for(int i = 1 ; i <= maxa ; ++ i) 
	{
		L[i] = R[i - 1] + 1;
		R[i] = L[i] + dc[i] - 1;
		dc[i] = L[i] - 1;
	}
	for(int i = 1 ; i <= maxa ; ++ i) 
		for(int j = i ; j <= maxa ; j += i) vs[++ dc[j]] = i;
	for(int i = 1 ; i <= n ; ++ i)
	{
		for(int j = L[a[i]] ; j <= R[a[i]] ; ++ j) ++ b[vs[j]] , p2[i] += B[vs[j]];
		p1[i] = p1[i - 1] + b[a[i]];
		++ B[a[i]];
		p2[i] += p2[i - 1];
	}
	sort(Sec + 1 , Sec + 1 + q , cmp);
	int l = 1 , r = 0;
	for(int i = 1 ; i <= q ; ++ i)
	{
		if(l > Sec[i].l)
		{
			ques[++ qcnt] = (Node){Sec[i].l , l - 1 , i , 1 , r};
			Sec[i].ans -= p1[l - 1] - p1[Sec[i].l - 1];
			Sec[i].ans -= p2[l - 1] - p2[Sec[i].l - 1];
			l = Sec[i].l;
		}
		if(r < Sec[i].r)
		{
			ques[++ qcnt] = (Node){r + 1 , Sec[i].r , i , -1 , l - 1};
			Sec[i].ans += p1[Sec[i].r] - p1[r];
			Sec[i].ans += p2[Sec[i].r] - p2[r];
			r = Sec[i].r;
		}
		if(l < Sec[i].l)
		{
			ques[++ qcnt] = (Node){l , Sec[i].l - 1 , i , -1 , r};
			Sec[i].ans += p1[Sec[i].l - 1] - p1[l - 1];
			Sec[i].ans += p2[Sec[i].l - 1] - p2[l - 1];
			l = Sec[i].l;
		}
		if(r > Sec[i].r)
		{
			ques[++ qcnt] = (Node){Sec[i].r + 1 , r , i , 1 , l - 1};
			Sec[i].ans -= p1[r] - p1[Sec[i].r];
			Sec[i].ans -= p2[r] - p2[Sec[i].r];
			r = Sec[i].r;
		}
	}
	//for(int i = 1 ; i <= q ; i ++) printf("%d\n",Sec[i].ans);
	sort(ques + 1 , ques + 1 + qcnt , cmd);
	idx = 0;
	memset(b , 0 , sizeof b);
	for(int i = 1 ; i <= qcnt ; ++ i)
	{
		if(ques[i].i <= 0) continue;
		while(idx < ques[i].i) 
		{
			idx ++;
			for(int j = L[a[idx]] ; j <= R[a[idx]]; j ++) ++ b[vs[j]];
			if(a[idx] > vt) for(int j = 1 ; a[idx] * j <= maxa ; ++ j) ++ b[a[idx] * j];
		}
		for(int j = ques[i].l ; j <= ques[i].r ; ++ j) Sec[ques[i].idx].ans += ques[i].op * b[a[j]];
	}
	//for(int i = 1 ; i <= q ; i ++) printf("%d\n",Sec[i].ans);
	for(int j = 1 ; j <= vt ; ++ j)
	{
		for(int i = 1 ; i <= n ; ++ i) pre[i] = pre[i - 1] + (a[i] % j == 0);
		idx = cnt = 0;
		for(int i = 1 ; i <= qcnt ; ++ i)
		{
			if(ques[i].i <= 0) continue;
			while(idx < ques[i].i)
			{
				++ idx;
				if(a[idx] == j) ++ cnt;
			}
			Sec[ques[i].idx].ans += 1LL * ques[i].op * (pre[ques[i].r] - pre[ques[i].l - 1]) * cnt;
		}
	}
	//for(int i = 1 ; i <= q ; i ++) printf("%d\n",Sec[i].ans);
	for(int i = 1 ; i <= q ; ++ i) Sec[i].ans += Sec[i - 1].ans;
	for(int i = 1 ; i <= q ; ++ i) Print[Sec[i].id] = Sec[i].ans;
	for(int i = 1 ; i <= q ; ++ i) write(Print[i]) , *O++='\n';
	fwrite(obuf,O-obuf,1,stdout);
	return 0;
}