#P14914. [UOI 2024 2S-1-5]GCD, Sum, Multiply. What?...

    ID: 14130 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400数论ST表树状数组二分数据结构前缀和数学

[UOI 2024 2S-1-5]GCD, Sum, Multiply. What?...

题目描述

出题人在前几题中已经耗尽了所有创意,所以这道题的题面不会再折磨 Anton。他只是给你一个有趣的问题。

给定一个由 nn 个整数组成的数组 aa。同时给定 qq 个询问 [l,r][l,r]。对于每个询问,请在所有满足以下条件的二元组 (tl,tr)(tl,tr) 中,求出 $\operatorname{sum}[tl,tr]\times \operatorname{gcd}[tl,tr]$ 的最大值:

  • l≤tl≤tr≤rl \le tl \le tr \le r;
  • sum⁡[tl,tr]\operatorname{sum}[tl,tr] 表示区间 [tl,tr][tl,tr] 中所有数的和;
  • gcd⁡[tl,tr]\operatorname{gcd}[tl,tr] 表示区间 [tl,tr][tl,tr] 中所有数的最大公约数。

两个数 aa 和 bb 的最大公约数,是同时整除 aa 和 bb 的最大正整数 xx。

一组数的最大公约数,是同时整除这组数中所有元素的最大正整数 xx。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤2⋅1051 \le n,q \le 2\cdot 10^5),分别表示数组元素个数和询问个数。

第二行包含 nn 个整数 aia_i(1≤ai≤6⋅1061 \le a_i \le 6\cdot 10^6),表示数组。

接下来 qq 行,每行包含两个整数 l,rl,r(1≤l≤r≤n1 \le l \le r \le n),表示一个询问。

输出格式

输出 qq 个整数,分别表示各个询问的答案。

输入 #1

3 2
3 3 2
1 3
2 3

输出 #1

18
9

子任务

  1. (44 分)n≤3n \le 3;
  2. (88 分)n,q≤103n,q \le 10^3;
  3. (55 分)n≤103n \le 10^3;
  4. (1717 分)n,q≤105n,q \le 10^5;
  5. (1414 分)n≤105n \le 10^5;
  6. (55 分)ai≤20a_i \le 20;
  7. (77 分)ai≤103a_i \le 10^3;
  8. (1616 分)l=1l=1;
  9. (2424 分)无额外限制。