题解||线段树

区间，公因数。

根据线段树的特性，因为公因数有结合律特性，所以可以用线段树进行求解。我们只需要用到建树函数和区间查询函数即可。

#include <bits/stdc++.h>
using namespace std;
namespace fast{
    #define int long long
    #ifdef __linux__
    #define gc getchar_unlocked
    #define pc putchar_unlocked
    #else
    #define gc _getchar_nolock
    #define pc _putchar_nolock
    #endif
    inline bool blank(const char x) {return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
    template<typename Tp> inline void read(Tp &x) {x=0; register bool z=true; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=(x<<1)+(x<<3)+(a^48); x=(z?x:~x+1);}
    inline void read(double &x) {x=0.0; register bool z=true; register double y=0.1; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=x*10+(a^48); if(a!='.') return x=z?x:-x,void(); for(a=gc();isdigit(a);a=gc(),y/=10) x+=y*(a^48); x=(z?x:-x);}
    inline void read(char &x) {for(x=gc();blank(x)&&(x^-1);x=gc());}
    inline void read(char *x) {register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) *x++=a; *x=0;}
    inline void read(string &x) {x=""; register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) x+=a;}
    template<typename T,typename ...Tp> inline void read(T &x,Tp &...y) {read(x),read(y...);}
    template<typename Tp> inline void write(Tp x) {if(!x) return pc(48),void(); if(x<0) pc('-'),x=~x+1; register int len=0; register char tmp[64]; for(;x;x/=10) tmp[++len]=x%10+48; while(len) pc(tmp[len--]);}
    inline void write(const double x) {register int a=6; register double b=x,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); pc('.'); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);}
    inline void write(const pair<int,double>x) {register int a=x.first; if(a<7) {register double b=x.second,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); a&&(pc('.')); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);} else cout<<fixed<<setprecision(a)<<x.second;}
    inline void write(const char x) {pc(x);}
    inline void write(const bool x) {pc(x?49:48);}
    inline void write(char *x) {fputs(x,stdout);}
    inline void write(const char *x) {fputs(x,stdout);}
    inline void write(const string &x) {fputs(x.c_str(),stdout);}
    template<typename T,typename ...Tp> inline void write(T x,Tp ...y) {write(x),write(y...);} 
}using namespace fast;
const int N=4000005;
vector<int> a(N);
class segment_tree{
    private:
        struct node{
            int lazy=0,data;
        }tree[N];
        int left_child(int now){//取左孩子，返回的是索引
            return 2*now;
        }int right_child(int now){//取右孩子
            return 2*now+1;
        }
    public:
        void build(int now,int l,int r){//递归建树
            tree[now].lazy=0;//懒标记的初始化，后面会讲
            if(l==r){//叶子节点
                tree[now].data=a[l];
                return ;
            }int mid=l+(r-l)/2;
            build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
            tree[now].data=__gcd(tree[left_child(now)].data,tree[right_child(now)].data);//赋值该节点为他的左右孩子节点值之和。
        }
        long long query_gcd(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
            if(ql>r or qr<l)return 0;
            if(ql<=l and qr>=r)return tree[now].data;
            int mid=l+(r-l)/2;
            return __gcd(query_gcd(left_child(now),l,mid,ql,qr),query_gcd(right_child(now),mid+1,r,ql,qr));
        }
};
signed main(){
    segment_tree tree;
    int n,m;
    read(n,m);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }tree.build(1,1,n);
    while(m--){
        int x,y;
        read(x,y);
        write(tree.query_gcd(1,1,n,x,y),"\n");
    }
    return 0;
}

时间复杂度： $\mathcal{O}(n+m\log n)$
空间复杂度： $\mathcal{O}(n)$