AT_abc254_f [ABC254F] Rectangle GCD

给定一个正整数 $N$，以及两个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 和 $B=(B_1,B_2,\dots,B_N)$。 有一个 $N \times N$ 的网格。第 $i$ 行第 $j$ 列的格子记为格子 $(i,j)$。对于所有满足 $1 \leq i,j \leq N$ 的整数对 $(i,j)$，在格子 $(i,j)$ 中写有 $A_i + B_j$。请处理 $Q$ 个如下的查询： - 给定满足 $1 \leq h_1 \leq h_2 \leq N, 1 \leq w_1 \leq w_2 \leq N$ 的整数 $h_1, h_2, w_1, w_2$，请你求出左上角为 $(h_1,w_1)$，右下角为 $(h_2,w_2)$ 的矩形区域内所有整数的最大公约数。

输入通过标准输入给出，格式如下： > $N$ $Q$ > $A_1$ $A_2$ $\dots$ $A_N$ > $B_1$ $B_2$ $\dots$ $B_N$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个查询的格式如下： > $h_1$ $h_2$ $w_1$ $w_2$

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

### 数据范围 - $1 \leq N, Q \leq 2 \times 10^5$ - $1 \leq A_i, B_i \leq 10^9$ - $1 \leq h_1 \leq h_2 \leq N$ - $1 \leq w_1 \leq w_2 \leq N$ - 输入均为整数。 ### 样例解释 1 设格子 $(i,j)$ 中写的整数为 $C_{i,j}$。对于第 $1$ 个查询，$C_{1,2}=4, C_{1,3}=6, C_{2,2}=6, C_{2,3}=8$，这些数的最大公约数为 $2$，因此答案为 $2$。 由 ChatGPT 4.1 翻译