Greatest of the Greatest Common Divisors

题意

给定一个长度为 $n$ 的序列 $a_i$ 和 $q$ 个询问，每个询问求出 $[l,r]$ 内所有数对的最大公约数中的最大值。

$n,q\leq10^5$ 。

思路

经典正难则反：不好直接求 GCD 就考虑约数的贡献。

然后类似扫描线的思想，离线后把时间作为一个维度处理区间信息，这里用树状数组维护区间内的最大约数。

代码

const int N = 1e5 + 10, M = 1e5;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	vector <int> d[N];
	int a[N];
	struct Query {
		int l, r, id, ans;
	}q[N];
	
	int f[N];
	int t[N];
	void mxe (int &x, int y) { if (x < y) x = y; }
	void modify (int x, int val) { for (; x; x -= x & -x) mxe(t[x], val); }
	int query (int x) { int ans = 0; for (; x <= n; x += x & -x) mxe(ans, t[x]); return ans; }
	
	int main () {
		for (int k = 1; k <= M; ++k)
			for (int i = k; i <= M; i += k) d[i].emplace_back(k);
		n = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		m = read();
		for (int i = 1; i <= m; ++i)
			q[i].l = read(), q[i].r = read(), q[i].id = i;
		sort(q + 1, q + 1 + m, [](Query a, Query b){return a.r < b.r;});
		int lst = 0, cur = 1;
		for (int i = 1; i <= n; ++i) {
			for (; cur <= m && q[lst + 1].r == q[cur].r && q[cur].r <= i; cur++);
			for (int j : d[a[i]]) {
				if (f[j]) modify(f[j], j);
				f[j] = i;
			}
			for (++lst; lst < cur; ++lst)
				q[lst].ans = query(q[lst].l);
			lst = cur - 1;
		}
		sort(q + 1, q + 1 + m, [](Query a, Query b){return a.id < b.id;});
		for (int i = 1; i <= m; ++i) printf ("%d\n", q[i].ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}