90分，long long爆MLE

#include<bits/stdc++.h>
using namespace std;
struct s{
    unsigned int lz,sum;
}t[4000005];
long long n,k,q,sum,p[1000005];
void pushup(int x,int l,int r){
    int mid=l+r>>1;
    t[x<<1].lz+=t[x].lz;
    t[x<<1|1].lz+=t[x].lz;
    t[x<<1].sum+=(mid-l+1)*t[x].lz;
    t[x<<1|1].sum+=(r-mid)*t[x].lz;
    t[x].lz=0;
}void modify(int x,int l,int r,int ql,int qr,int v){
    if(l>=ql&&r<=qr){
        t[x].lz+=v;
        t[x].sum+=(r-l+1)*v;
        return;
    }pushup(x,l,r);
    int mid=l+r>>1;
    if(ql<=mid) modify(x<<1,l,mid,ql,qr,v);
    if(qr>mid) modify(x<<1|1,mid+1,r,ql,qr,v);
    t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}long long qurry(int x,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return t[x].sum;
    pushup(x,l,r);
    long long mid=l+r>>1,res=0;
    if(mid>=ql) res=qurry(x<<1,l,mid,ql,qr);
    if(qr>mid) res+=qurry(x<<1|1,mid+1,r,ql,qr);
    return res;
}void st(int x,int v){
    for(int i=1;i<=n;i+=x) modify(1,1,n,i,i,v);
}int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        p[x]++;
    }for(int i=1;i<=n;i++){
        if(p[i]) st(i,p[i]);
    }cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<qurry(1,1,n,l+1,r+1)<<"\n";
    }return 0;
}