TLE#2#3#4，孩子已经傻了

#include<bits/stdc++.h>
#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;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9') ch=getchar();
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct query
{
    int l,r,bl,id;
    bool operator<(const query& zhouAKngyangAKIOI){return (bl<zhouAKngyangAKIOI.bl)||(bl==zhouAKngyangAKIOI.bl&&r<zhouAKngyangAKIOI.r);}
}q[500003];
struct Query
{
    int k,l,r,op,id;
    bool operator<(const Query& zhouAKngyangAKIOI){return k<zhouAKngyangAKIOI.k;}
}v[1000003];
vector<int> ys[500003];
int a[500003],cnt[500003],tcnt[103],B,b[500003];
long long ans[500003],lxl[500003],pre3[500003],c[500003];
int n,m,vcnt;
signed main()
{
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    // double S=clock();
    n=read(),m=read();
    for(int i=1; i<=n; ++i) b[i]=a[i]=read();
	sort(b+1,b+n+1);
	for(int i=n; i>=1; --i) c[i]=c[i+1]+b[n]/b[i];
	int pnt=1;
	long long mint=0x3f3f3f3f3f3f3f3f;
	for(int i=1; i*i<=n; ++i) 
    {
		while(pnt<=n&&b[pnt]<i) ++pnt;
		if((11ll*n*i>>1)+c[pnt]<mint) B=i,mint=(11ll*n*i>>1)+c[pnt];
	}
    ++B;
    for(int i=1; i<=500000; ++i) for(int j=1; i*j<=500000; ++j) ys[i*j].push_back(i);
    for(int i=1; i<=m; ++i) q[i].l=read(),q[i].r=read(),q[i].bl=q[i].l/700,q[i].id=i;
    for(int i=1; i<=n; ++i) 
    {
        pre3[i]=pre3[i-1]+cnt[a[i]];
        for(int x:ys[a[i]]) ++cnt[x];
        for(int j=1; j<=B; ++j) if(a[i]%j==0) pre3[i]+=tcnt[j];
        if(a[i]>B) for(int j=1; a[i]*j<=500000; ++j) ++cnt[a[i]*j]; else ++tcnt[a[i]];
    }
    sort(q+1,q+m+1);
    for(int i=1,l=1,r=0; i<=m; ++i)
    {
        if(q[i].l<l) v[++vcnt]=(Query){r,q[i].l,l-1,1,i},ans[i]-=pre3[l-1]-pre3[q[i].l-1]+((l-q[i].l)<<1),l=q[i].l;
        if(q[i].r>r) v[++vcnt]=(Query){l-1,r+1,q[i].r,-1,i},ans[i]+=pre3[q[i].r]-pre3[r],r=q[i].r;
        if(q[i].l>l) v[++vcnt]=(Query){r,l,q[i].l-1,-1,i},ans[i]+=pre3[q[i].l-1]-pre3[l-1]+((q[i].l-l)<<1),l=q[i].l;
        if(q[i].r<r) v[++vcnt]=(Query){l-1,q[i].r+1,r,1,i},ans[i]-=pre3[r]-pre3[q[i].r],r=q[i].r;
    }
    sort(v+1,v+vcnt+1),memset(cnt,0,sizeof(cnt));
    for(int i=1,pos=0; i<=vcnt; ++i)
    {
        while(pos<v[i].k)
        {
            ++pos;
            for(int x:ys[a[pos]]) ++cnt[x];
            if(a[pos]>B) for(int j=1; a[pos]*j<=500000; ++j) ++cnt[a[pos]*j];   
        }
        for(int j=v[i].l; j<=v[i].r; ++j) ans[v[i].id]+=v[i].op*cnt[a[j]];
    }
    for(int k=1; k<=B; ++k)
    {
        for(int i=1; i<=n; ++i) cnt[i]=cnt[i-1]+(a[i]%k==0);
        for(int i=1,qwq=0,pos=0; i<=vcnt; ++i) 
        {
            while(pos<v[i].k) if(a[++pos]==k) ++qwq;
            ans[v[i].id]+=1ll*v[i].op*(cnt[v[i].r]-cnt[v[i].l-1])*qwq;
        }
    }
    for(int i=1; i<=m; i++) ans[i]+=ans[i-1];
    for(int i=1; i<=m; ++i) lxl[q[i].id]=ans[i]+q[i].r-q[i].l+1;
    for(int i=1; i<=m; ++i) printf("%lld\n",lxl[i]);
    // double T=clock();
    // cerr<<(T-S)/CLOCKS_PER_SEC<<endl;
	// cerr<<B<<endl;
    return 0;
}