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

输入 #1

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

输出 #1

2
1
11
6
10

输入输出样例 #2

输入 #2

1 1
9
100
1 1 1 1

输出 #2

109

说明/提示

数据范围

• $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 翻译