P1890gcd区间(爱思创题解）-创新互联

给定一行n个正整数a[1]…a[n]。

m次询问，每次询问给定一个区间[L,R]，输出a[L]~a[R]的大公因数。

第一行两个整数n，m。

第二行n个整数表示a[1]…a[n]。

以下m行，每行2个整数表示询问区间的左右端点。

保证输入数据合法。

共m行，每行表示一个询问的答案。

5 3 4 12 3 6 7 1 3 2 3 5 5

1 3 7

对于30%的数据，n<= 100， m<= 10

对于60%的数据，m<= 1000

对于100%的数据，1<= n<= 1000，1<= m<= 1,000,000

0< 数字大小<= 1,000,000,000

我们看题不难发现题目是寻找a[L]~a[R]这片区间之内的一个最值问题。不过这题中是求区间内的大公因数，区间！所以，要求：多次求解连续区域 a ∼ b a\sim b a∼b 的大公因数。我们能想到什么？很明显！求区间最值问题的ST表,ST表不懂的看这里。

#includeusing namespace std;

typedef long long ll;
const int N = 100010;

int maxn[N][50];    //区间大值表
int lg[N];  //lg函数,其实就是课上讲的Log[N]

inline int read(){//快速输入
    int x = 0,f=1;char ch = getchar();
    while(ch< '0' || ch >'9') {if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch<= '9'){x = x*10 + ch - '0'; ch = getchar();}
    return x*f;
}

int main(){int n,m;
    n = read(); m = read();

    for(int i = 1;i<=n;i++){//初始化
        maxn[i][0] = read();
    }

    for(int i = 2;i<=n;i++){//以2为底的lg求出来 ,最少要求到lgn，因为我们是通过2^i去倍增区间长度的
        lg[i] = lg[i/2] + 1;
    }

    for(int i = 1;i<=lg[n];i++)     //建立st表，第一维是区间起始位置，第二维终止位置是2^i-1
        for(int j = 1;j + (1<maxn[j][i] = max(maxn[j][i-1],maxn[j+(1<<(i-1))][i-1]);
        }

    int l,r;
    while(m--){l = read(); r = read();

        int len = lg[r-l+1];

        //查询，求两个子区间的并集，，第二个区间的左端点，这个端点我们不知道
        //就假设它为x，那么x + (1<

int gcd(int a,int b)
{int r=a%b;
	while(r>0)
	{a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);//递归+三目运算符
}

#includeusing namespace std;
const int N = 1e5+5;
int st[N][20];
int logg[N];
int n,m;
int gcd(int a,int b)
{if(b==0) return a;
	else return gcd(b,a%b);	
} 
int main()
{	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){scanf("%d",&st[i][0]);
	}
	for(int i=2;i<=n;i++) logg[i]=logg[i/2]+1;
	
	for(int j=1;j<=logg[n];j++){for(int i=1;i+(1<	st[i][j]=gcd(st[i][j-1],st[i+(1<scanf("%d%d",&l,&r);
		int x=logg[r-l+1];
		printf("%d\n",gcd(st[l][x],st[r-(1<