官方题解只能做到 $O(T \sqrt {V} + n \log n + n \log V + n\cdot d(V))$？玩的太差了。这题可以做到确定性 $O(n+\sqrt[3]{V}\log V)$ 时间、$O(n+\sqrt[3]{V})$ 空间，其中 $V=\max b_i$。关键不只是枚举可能的 $x$，而是证明：经过一次精心选择的筛选后，候选数量与需要分别处理的约束数量之积只有 $O(\sqrt[3]{V})$，从而去掉逐个候选扫描整个序列的乘法项。
常规做法是枚举一个最大公约数的约数，再逐个检查笛卡尔树上的条件；官方题解也采用了这个方向。下面进一步优化这一过程，并使用确定性整数分解，避免约数枚举本身退化到 $O(\sqrt V)$。([Universal Cup Judging System][1])
题解
题目要求：对于加上 $x$ 后的序列，每个非空区间中都存在一个元素，能够整除该区间的所有元素。由于元素均为正数，这个元素只能是区间最小值。题目中 $n\le 5\times10^4$，$b_i,k\le10^9$。([QOJ][2])
首先建立原序列的小根笛卡尔树。所有元素同时加上 $x$ 不改变大小关系，因此树的结构与 $x$ 无关。题目条件等价于：对于笛卡尔树的每条父子边，父节点对应的数都整除子节点对应的数。
必要性来自父节点的整棵子树：它对应一个连续区间，最小值就是父节点的值。充分性则是因为任意区间的最小值节点，都是区间内其他节点的祖先，沿树边传递整除关系即可。于是，不需要枚举区间，也不需要建立区间 gcd 数据结构，只需在线性时间内建立笛卡尔树。
令 $m=\min b_i$，$G=\gcd(b_1-m,b_2-m,\ldots,b_n-m)$。如果 $G=0$，所有元素相同，任何 $1\le x\le k$ 都合法，直接输出 $k$ 和 $k(k+1)/2$。
以下考虑 $G>0$。整个序列的最小值 $m+x$ 必须整除所有元素，因此必有 $m+x\mid G$。记 $t=G/(m+x)$，那么 $t$ 是 $G$ 的正约数，且 $x=G/t-m$。再记 $c_i=(b_i-m)/G$，便有 $b_i+x=(m+x)(1+c_it)$。
考虑一条父子边 $u\to v$。其整除条件变成 $(1+c_ut)\mid(1+c_vt)$。由于 $\gcd(1+c_ut,t)=1$，这个条件又等价于
$$ 1+c_ut\mid c_v-c_u. $$
父子值相等的边自动满足条件；$c_u=0$ 的边也自动满足条件。剩下的每条边都可以表示为一个约束 $(c,d)$，其中 $c\ge1,d\ge1$，要求 $ct+1\mid d$。
假如没有剩余约束，只需枚举 $G$ 的约数，统计满足 $1\le G/t-m\le k$ 的那些约数。
否则，选取 $c$ 最大 的一条约束，记为 $(C,D)$；如果存在多条这样的约束，可以选择其中 $D$ 最小的一条。先筛出所有满足 $t\mid G$、$Ct+1\mid D$ 以及答案范围限制的候选，记剩余数量为 $R$。
筛选时不一定要分解 $G$。当 $G\le D$ 时，枚举 $G$ 的约数 $t$；当 $D< G$ 时，枚举 $D$ 的约数 $z$，由 $z=Ct+1$ 得到 $t=(z-1)/C$，再检查它是否为 $G$ 的约数。这样只需要分解 $\min(G,D)$。注意 $GD$ 恰好是所选树边两端原始数值的差，所以 $GD< V$，进而 $\min(G,D)<\sqrt V$。
下面是控制复杂度的关键。
若筛选后有 $R\ge3$ 个候选，则 $C(R-2)< \sqrt[3]{GD}<\sqrt[3]V$。
证明如下。取剩余候选中最大的三个，记为 $t_1< t_2< t_3$，并令 $u_i=Ct_i+1$。由于 $t_i$ 都是 $G$ 的约数，而 $u_i$ 都是 $D$ 的约数，有 $\operatorname{lcm}(t_1,t_2,t_3)\mid G$ 和 $\operatorname{lcm}(u_1,u_2,u_3)\mid D$。
对任意 $i< j$，设 $g=\gcd(t_i,t_j)$，写成 $t_i=ga,t_j=gb$。根据 $bu_i-au_j=b-a$，可知 $\gcd(u_i,u_j)\mid b-a$，从而 $\gcd(t_i,t_j)\gcd(u_i,u_j)\le t_j-t_i$。
另一方面，三个正整数的最小公倍数不小于它们的乘积除以三个两两最大公约数的乘积。将这个结论分别用于 $t_i$ 和 $u_i$，再将两式相乘，得到
$$ GD\ge \frac{t_1t_2t_3u_1u_2u_3} {(t_2-t_1)(t_3-t_1)(t_3-t_2)} > \frac{C^3(t_1t_2t_3)^2}{t_2t_3^2} = C^3t_1^2t_2 > C^3t_1^3. $$
因为这是 $R$ 个不同正整数中最大的三个，必有 $t_1\ge R-2$，所需结论得证。
这个不等式同时解决了两个问题。
当 $R\le2$ 时，直接对每个候选扫描全部树边，时间就是 $O(n)$。
当 $R\ge3$ 时，必有 $C<\sqrt[3]V$。所有约束的 $c$ 都在 $[1,C]$ 内，因此可以直接开一个长度为 $C+1$ 的数组，不需要排序，也不需要哈希表。对于所有第一项相同的约束 $(c,d)$，把它们合并为 $h_c=\gcd(d_1,d_2,\ldots)$，之后只需检查 $ct+1\mid h_c$。
每个候选至多检查 $C$ 个位置，全部检查的次数不超过 $CR=2C+C(R-2)=O(\sqrt[3]V)$。因此，候选验证部分的总时间是 $O(n+\sqrt[3]V)$，而不是 $O(nR)$。
还需要把 gcd 和整数分解的代价算进去。对同一组数依次求 gcd，累计复杂度是“该组元素数量加 $O(\log V)$”，而不是每个元素都乘上 $\log V$：每次调用除去常数步后，剩余欧几里得迭代可以摊到当前 gcd 的缩小上。因此，全部约束合并的时间为 $O(n+C\log V)=O(n+\sqrt[3]V\log V)$。
整数分解使用 Lehman 算法。它先试除到 $\lceil N^{1/3}\rceil$，之后对 $4qN$ 进行短区间平方差搜索。Lehman 定理保证，若尚未找到因子且 $N$ 为合数，就能在这些区间中找到非平凡因子；所有搜索区间的总长度为 $O(N^{1/3})$。下面的实现采用这一确定性方法，而非随机分解。([arXiv][3])
计入 gcd 的代价，整数分解同样可以放进 $O(\sqrt[3]V\log V)$ 的上界。分解后生成约数的时间为 $O(\tau(N))$，利用 $\tau(N)=O(N^{1/3})$，也不会成为瓶颈。
因此，最终的确定性时间复杂度为 $O(n+\sqrt[3]V\log V)$，空间复杂度为 $O(n+\sqrt[3]V)$。其中关于 $n$ 的部分已经是线性的。
代码：https://qoj.ac/submission/2936317 。区域赛的题目就是简单。