>Link

ybtoj静态区间

luogu P1890

---

>解题思路

其实就是ST表的模板套上一个gcd就行了
算了一下时间复杂度，大概 O ( n l o g n l o g a i ) O(nlognloga_i) O(nlognlogai​)（?）差不多可以过的

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
using namespace std;

int n, m, a[N], f[N][30], lg[N];

int gcd (int a, int b)
{
	if (a == 1 || b == 1) return 1;
	if (a == b || !b) return a;
	return gcd (b, a % b);
}

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf ("%d", &f[i][0]);
	for (int i = 1; i <= n; i++)
	  lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	for (int i = 1; i <= lg[n] - 1; i++)
	  for (int j = 1; j <= n - (1 << i) + 1; j++)
	    f[j][i] = gcd (f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
	int l, r;
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d", &l, &r);
		int x = lg[r - l + 1] - 1;
		printf ("%d\n", gcd (f[l][x], f[r - (1 << x) + 1][x]));
	}
	return 0;
}