已经交了 4 发全 T 了，本地随机数据差不多都是 2.5 s 左右。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=5e5+5,B=710;
ll ans[N],ans2[N],s[N];
int n,m,V,a[N],c[N],t[N],num[N],vis[N],pd[N];
struct node{int l,r,w,id;} q[N];
vector<int> p[N];
vector<node> v[N];

char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
    int x=0;char c=nc();
    for(;!isdigit(c);c=nc());
    for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
    return x;
}

int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    n=rd(),m=rd();
    clock_t st=clock(),ed;
    for(int i=1;i<=n;i++) V=max(V,a[i]=rd()),vis[a[i]]=1,num[i]=num[i-1]+(a[i]>=B);
    for(int i=1;i<=m;i++) q[i]={rd(),rd(),0,i},ans2[i]=num[q[i].r]-num[q[i].l-1];
    for(int i=1;i<=V;i++) for(int j=i;j<=V;j+=i) p[j].push_back(i);
    for(int j=1;j<B;j++)
    {
        if(!vis[j]) continue;
        for(int i=1;i<=V;i++) pd[i]=0;for(int i=j;i<=V;i+=j) pd[i]=1;
        for(int i=1;i<=m;i++) ans2[i]+=(s[q[i].r]-s[q[i].l-1])*(c[q[i].r]-c[q[i].l-1]);
    }
    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        if(x<B) {s[i]=s[i-1];continue;}
        s[i]=s[i-1]+t[x];
        for(int j=x;j<=V;j+=x) t[j]++;
        for(int j:p[x]) t[j]++;
    }
    sort(q+1,q+1+m,[&](node a,node b){return a.l/B==b.l/B?a.r<b.r:a.l<b.l;});
    for(int i=1,l=1,r=0;i<=m;i++)
    {
        if(l>q[i].l) ans[q[i].id]-=s[l-1]-s[q[i].l-1],v[r].push_back({q[i].l,l-1,1,q[i].id}),l=q[i].l;
        if(r<q[i].r) ans[q[i].id]+=s[q[i].r]-s[r],v[l-1].push_back({r+1,q[i].r,-1,q[i].id}),r=q[i].r;
        if(l<q[i].l) ans[q[i].id]+=s[q[i].l-1]-s[l-1],v[r].push_back({l,q[i].l-1,-1,q[i].id}),l=q[i].l;
        if(r>q[i].r) ans[q[i].id]-=s[r]-s[q[i].r],v[l-1].push_back({q[i].r+1,r,1,q[i].id}),r=q[i].r;
    }
    memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        if(x>=B)
        {
            for(int j=x;j<=V;j+=x) t[j]++;
            for(int j:p[x]) t[j]++;
        }
        for(auto &[l,r,w,id]:v[i]) for(int j=l;j<=r;j++) if(a[j]>=B) ans[id]+=(t[a[j]]-2*(j<=i))*w;
    }
    for(int i=1;i<=m;i++) ans[q[i].id]+=ans[q[i-1].id];
    for(int i=1;i<=m;i++) cout<<ans[i]+ans2[i]<<'\n';
    ed=clock();
    cout<<"time :"<<(double)(ed-st)/CLOCKS_PER_SEC<<'\n';
}