珂朵莉与GCD

/**
 *    author:  MySakure
 *    created: 15.10.2019 20:15:26
**/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int maxn=1e5+10;
const int mod=1e9+7;
int a[maxn],n,m,ans[maxn],id=1;
struct q{
    int l,r,id;
}Q[maxn];
bool cmp(const q&a,const q&b){
    return a.r==b.r?a.l<b.l:a.r<b.r;
}
struct G{
    int l,r,g;
}tg[maxn<<2];
inline int read(){
    int sgn = 1; int cnt = 0;   //sgn表示正负号 cnt表示读取的数字
    char ch = getchar();
    while (ch < '0' || ch > '9') {      //读取非数字的字符，保留负号，忽略其余无关符号
        if(ch == '-')
            sgn = -sgn;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        cnt = cnt*10 + (ch-'0');
        ch = getchar();
    }
    return  sgn*cnt;
}
void buildg(int u,int l,int r){
    tg[u].l=l,tg[u].r=r;
    if(l==r){
        tg[u].g=0;
        return;
    }
    int mid=(l+r)>>1;
    buildg(u<<1,l,mid);
    buildg(u<<1|1,mid+1,r);
    tg[u].g=0;
}
void updateg(int u,int L,int R,int v){
    int l=tg[u].l,r=tg[u].r;
    if(tg[u].g){
        tg[u].g=__gcd(tg[u].g,v);
        return;
    }
    if(l==r){
        if(tg[u].g==0)tg[u].g=v;
        return;
    }
    int mid=(l+r)>>1;
    if(L>mid)updateg(u<<1|1,L,R,v);
    else if(R<=mid)updateg(u<<1,L,R,v);
    else updateg(u<<1,L,mid,v),updateg(u<<1|1,mid+1,R,v);
    if(tg[u<<1].g&&tg[u<<1|1].g&&__gcd(tg[u<<1|1].g,v)==__gcd(tg[u<<1].g,v)){
        tg[u].g=__gcd(tg[u<<1].g,v);
    }
}
int Quareg(int u,int pos){
    int l=tg[u].l,r=tg[u].r;
    if(l==r||tg[u].g){
        return tg[u].g;
    }
    int mid=(l+r)>>1;
    if(pos>mid)return Quareg(u<<1|1,pos);
    else return Quareg(u<<1,pos);
}
struct s{
    int l,r,s;
    int lazy;
}t[maxn<<2];
void build(int u,int l,int r){
    t[u].l=l,t[u].r=r;
    if(l==r){
        t[u].s=0;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}
void pushdown(int u){
    t[u<<1].s+=(t[u<<1].r-t[u<<1].l+1)%mod*t[u].lazy%mod;
    t[u<<1].s%=mod;
    t[u<<1].lazy+=t[u].lazy;
    t[u<<1|1].s+=(t[u<<1|1].r-t[u<<1|1].l+1)%mod*t[u].lazy%mod;
    t[u<<1|1].s%=mod;
    t[u<<1|1].lazy+=t[u].lazy;
    t[u].lazy=0;
}
void update(int u,int L,int R,int pos){
    int l=t[u].l,r=t[u].r;
    int mid=(l+r)>>1;
   // cerr<<"update ing "<<pos<<endl;
    if(l!=r)pushdown(u);
    if(l==L&&R==r){
        //cerr<<"hahah "<<pos<<endl;
        int gl=Quareg(1,l),gr=Quareg(1,r);
        //cerr<<pos<<" update "<<" "<<r<<" "<<gr<<endl;
        //cerr<<pos<<" update "<<" "<<l<<" "<<gl<<endl;
        if(gl==gr||l==r){
            //cerr<<pos<<" update "<<l<<" "<<r<<" "<<gl<<endl;
            t[u].s+=(t[u].r-t[u].l+1)*gl%mod;
            t[u].s%=mod;
            t[u].lazy+=gl;
        }
        else{
            update(u<<1,L,mid,pos);
            update(u<<1|1,mid+1,R,pos);
            t[u].s=t[u<<1].s+t[u<<1|1].s;
            t[u].s%=mod;
        }
        return;
    }
    if(L>mid)update(u<<1|1,L,R,pos);
    else if(R<=mid)update(u<<1,L,R,pos);
    else {
        update(u<<1,L,mid,pos);
        update(u<<1|1,mid+1,R,pos);
    }
    t[u].s=t[u<<1].s+t[u<<1|1].s;
    t[u].s%=mod;
}
int Quaresum(int u,int L,int R){
    int l=t[u].l,r=t[u].r;
    int mid=(l+r)>>1;
    if(l!=r)pushdown(u);
    if(l==L&&r==R){
        return t[u].s;
    }
    if(L>mid)return Quaresum(u<<1|1,L,R);
    else if(R<=mid)return Quaresum(u<<1,L,R);
    else return (Quaresum(u<<1,L,mid)+Quaresum(u<<1|1,mid+1,R))%mod;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef mysakure
    freopen("in1.txt","r",stdin);
#endif
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i){
        Q[i].l=read();Q[i].r=read();
        if(Q[i].l>Q[i].r){
            swap(Q[i].l,Q[i].r);
        }
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m,cmp);
    buildg(1,1,n);
    build(1,1,n);
    for(int i=1;i<=n;++i){
        updateg(1,1,i,a[i]);
        update(1,1,i,i);
        while(Q[id].r==i&&id<=m){
            ans[Q[id].id]=Quaresum(1,Q[id].l,Q[id].r);
            ++id;
        }
    }
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
    return 0;
}