P15741 [JAG 2024 Summer Camp #2] Max Sum of GCD

对于一个由正整数构成的序列 $\boldsymbol{X} = (X_1, X_2, \ldots, X_M)$（其中 $M \geq 2$），定义 $f(\boldsymbol{X})$ 为以下问题的答案： - 在 $M$ 个正整数 $X_1, X_2, \ldots, X_M$ 中，将至少一个、至多 $M - 1$ 个数涂成红色，其余数涂成蓝色。令 $R$ 为所有被涂成红色的数的最大公约数（GCD），$B$ 为所有被涂成蓝色的数的最大公约数。求 $R + B$ 可能的最大值。 给定一个由 $N$ 个正整数构成的序列 $\boldsymbol{A} = (A_1, A_2, \ldots, A_N)$。接下来会给出 $Q$ 个查询。对于每个查询，会给定两个整数 $l_i$ 和 $r_i$，满足 $1 \leq l_i < r_i \leq N$。对于每个查询，令 $\boldsymbol{X} = (A_{l_i}, A_{l_i + 1}, \ldots, A_{r_i})$，求 $f(\boldsymbol{X})$。

输入以如下格式给出： $$ \begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \\ &Q \\ &l_1 \ r_1 \\ &l_2 \ r_2 \\ &\vdots \\ &l_Q \ r_Q \end{aligned} $$ - $2 \leq N \leq 200,000$ - 对于所有 $1 \leq i \leq N$，有 $1 \leq A_i \leq 10^{18}$ - $1 \leq Q \leq 200,000$ - 对于所有 $1 \leq i \leq Q$，有 $1 \leq l_i < r_i \leq N$

输出 $Q$ 行。在第 $i$ 行（$1 \leq i \leq Q$）输出第 $i$ 个查询的答案。

翻译由 DeepSeek V3.2 完成