怎么求二维区间的最大公约数

我们可以使用线段树来解决这个问题。对于每个区间，我们都可以预处理出其内部所有数的最大公约数，然后在询问时，查询覆盖该询问区间的所有区间的最大公约数并取最大值即可。

具体地，我们可以将二维区间 $(i,j)$ 分别看作 $i$ 和 $j$ 两个维度，建立一颗二维线段树。对于每个节点 $(x,y)$，它表示的区间为 $[l_x,r_x]\times[l_y,r_y]$，其中 $l_x,r_x,l_y,r_y$ 分别表示该节点在 $x$ 和 $y$ 维度上的左右边界。我们可以在每个节点上维护一个值 $g_{x,y}$，表示区间 $[l_x,r_x]\times[l_y,r_y]$ 内部所有数的最大公约数。

对于每个节点 $(x,y)$，我们可以通过递归地计算其左右儿子节点的 $g$ 值来求出该节点的 $g$ 值。具体地，我们可以将节点 $(x,y)$ 表示的区间分成四个子区间，分别为 $[l_x,\lfloor\frac{l_x+r_x}{2}\rfloor]\times[l_y,\lfloor\frac{l_y+r_y}{2}\rfloor]$、$[\lfloor\frac{l_x+r_x}{2}\rfloor+1,r_x]\times[l_y,\lfloor\frac{l_y+r_y}{2}\rfloor]$、$[l_x,\lfloor\frac{l_x+r_x}{2}\rfloor]\times[\lfloor\frac{l_y+r_y}{2}\rfloor+1,r_y]$ 和 $[\lfloor\frac{l_x+r_x}{2}\rfloor+1,r_x]\times[\lfloor\frac{l_y+r_y}{2}\rfloor+1,r_y]$。然后我们可以递归地计算出这四个子区间的 $g$ 值，然后将它们合并起来得到该节点的 $g$ 值。合并方法为取四个子区间的 $g$ 值的最大公约数。

查询时，我们从根节点开始，递归地查找覆盖询问区间的节点，并将这些节点的 $g$ 值取最大值。具体地，对于当前节点 $(x,y)$，如果它表示的区间与询问区间不相交，则直接返回 1。否则，如果它表示的区间完全包含询问区间，则返回该节点的 $g$ 值。否则，我们将询问区间分成四个子区间，并递归地查询每个子区间，然后将它们的 $g$ 值取最大公约数作为当前节点的 $g$ 值返回。

时间复杂度为 $O((n+m)\log^2(n+m))$，其中 $n$ 和 $m$ 分别为二维区间的行数和列数。空间复杂度为 $O((n+m)\log^2(n+m))$。