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 \le i,j \le N$ 的整数对 $(i,j)$，方格 $(i,j)$ 上写着整数 $A_i + B_j$。处理 $Q$ 个如下形式的查询。

给定整四元组 $h_1,h_2,w_1,w_2$，满足 $1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N$。求由左上角为 $(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$ 行应包含 $\mathrm{query}_i$ 的答案。

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

2
1
11
6
10

1 1
9
100
1 1 1 1

109

提示

$1 \le N,Q \le 2 \times 10^5$ $1 \le A_i,B_i \le 10^9$ $1 \le h_1 \le h_2 \le N$ $1 \le w_1 \le w_2 \le N$ 输入中的所有值均为整数。记 $C_{i,j}$ 为方格 $(i,j)$ 上的整数。 对于第 $1$ 个查询，有 $C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8$，因此答案为它们的最大公约数，即 $2$。

标签: AtCoder|abc254F

来源

AtCoder|abc254F