P15066 [UOI 2024 II Stage] GCD, Sum, Multiply. What?...

出题人已将创意全数用于之前的题目，因此本题不会在题面上为难 Anton。他只是给你一个有趣的问题。 给定一个由 $n$ 个整数组成的数组 $a$。同时给出 $q$ 个查询 $[l;r]$。对于每个查询，找出所有对 ($tl;tr$) 中 $\operatorname{sum}[tl;tr] \times \operatorname{gcd}[tl;tr]$ 的最大值，其中 - $l \le tl \le tr \le r$； - $\operatorname{sum}[tl;tr]$ —— 区间 $[tl;tr]$ 内所有数的和； - $\operatorname{gcd}[tl;tr]$ —— 区间 $[tl;tr]$ 内所有数的最大公约数。 两个数 $a$ 和 $b$ 的最大公约数是指能同时整除 $a$ 和 $b$ 的最大正整数 $x$。 一组数的最大公约数是指能整除该组所有元素的最大正整数 $x$。

- 第一行包含两个整数 $n$、$q$（$1 \le n, q \le 2 \cdot 10^5$）——分别表示数组的元素个数和查询个数。 - 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 6 \cdot 10^6$）——数组的描述。 - 接下来的 $q$ 行，每行包含两个整数 $l$、$r$（$1 \le l \le r \le n$）——查询的描述。

输出 $q$ 个整数——每个查询的答案。

在第一个示例中，存在以下区间： - $[1;1]$ —— $\operatorname{sum}[1;1] \times \operatorname{gcd}[1;1]$ = $3 \times 3$ = $9$； - $[1;2]$ —— $\operatorname{sum}[1;2] \times \operatorname{gcd}[1;2]$ = $6 \times 3$ = $18$； - $[1;3]$ —— $\operatorname{sum}[1;3] \times \operatorname{gcd}[1;3]$ = $8 \times 1$ = $8$； - $[2;2]$ —— $\operatorname{sum}[2;2] \times \operatorname{gcd}[2;2]$ = $3 \times 3$ = $9$； - $[2;3]$ —— $\operatorname{sum}[2;3] \times \operatorname{gcd}[2;3]$ = $5 \times 1$ = $5$； - $[3;3]$ —— $\operatorname{sum}[3;3] \times \operatorname{gcd}[3;3]$ = $2 \times 2$ = $4$。 ### 评分细则 - （$4$ 分）：$n \le 3$； - （$8$ 分）：$n, q \le 10^3$； - （$5$ 分）：$n \le 10^3$； - （$17$ 分）：$n, q \le 10^5$； - （$14$ 分）：$n \le 10^5$； - （$5$ 分）：$a_i \le 20$； - （$7$ 分）：$a_i \le 10^3$； - （$16$ 分）：$l = 1$； - （$24$ 分）：无额外限制。 翻译由 DeepSeek V3 完成