笛卡尔树

Problem - M - Codeforces

同分治的思路，可以把区间分成：只在 \(mid\) 左边，只在 \(mid\) 右边，包含 \(mid\)。只不过这里的 \(mid\) 取的不是中点，而是最小值点，因此层数不是分治的那样。

对于一个 \(mid\) 管辖的区间，不妨假设 \(a_{mid} + x | \gcd(a_{mid} + x, a_{1}+x, a_{2}+x,\cdots)\)，同时 \(\gcd(a_{mid}+x,a_1+x,a_2+2,\cdots)\) 可以化成 \(\gcd(a_{mid} + x, c_1, c_2,\cdots)\)，其中 \(c\) 项代表不包含 \(x\)。

笛卡尔树可以用栈维护右链，线性时间内构建出来。 约束信息可以在笛卡尔树上快速合并，即用 \(a_{mid}+x\) 去减 \(a_{lmid}+x\) 和 \(a_{rmid}+x\)，从而它们也不包含 \(x\)，进而维护出上面形式的信息。

这样，大致可以 \(O(n\log(B))\) 求出，笛卡尔树的 \(n\) 个结点对应了 \(n\) 条形如 \(b_{i}+x | g_i\) 的约束（全部都满足就是充要条件了）。随便取一个约束（如果取不出非 \(0\) 的 \(g\) 代表完全没有约束，平凡，特判掉即可），就可以把 \(x\) 的取值范围缩减到因数数量级别。（冷知识：1e9 内因数数量最大是 1344）。

然后枚举这么多 \(x\)，看看是否符合全部 \(n\) 个约束即可。