[SNCPC2024] 猜质数 II

为了悄悄准备一个神秘的质数，MCPlayer542 伤透了脑筋。 随后他发明了一种~~聪明~~愚蠢的办法，并起名为“质数分”。 他准备了 $n$ 个不同的数 $a_1,\ a_2,\ \ldots,\ a_n$ 作为测试点，并定义“质数分” $score(x,l,r)$ 如下： $$score(x,l,r)=\sum_{i=l}^r{f(x,a_i)}$$ 其中 $$f(x,y)=\left\{\begin{array}{rcl}u-y, & x=1 \\ u, & 1<x\le y,\ \gcd(x,y)=1 \\ -x\cdot y, & x\neq 1,\ \gcd(x,y)=x \\ 0, & \text{otherwise} \end{array}\right.$$ 可见质数的“质数分”通常会比较高~~但还是没什么卵用~~。 于是 MCPlayer542 急了，现在他只想暴力乱测，并得到一个得分和 $\sum_{i=1}^{10^6}{score(i,l,r)}$。他打算测试 $q$ 次，每次测试给定 $u$ 和 $l$，其中 $u$ 为函数 $f(x,y)$ 的参数。 对于每次询问，他想知道所能得到的最大得分和以及能得到这个最大得分和的最小 $r$ 是多少。

输入数据的第一行包含两个整数 $n,\ q$ ($1\le n,\ q\le 5\times 10^5$)，用单个空格分隔。 第二行包含 $n$ 个整数 $a_1,\ a_2,\ \ldots,\ a_n$ ($1\le a_i\le 10^6$)，用单个空格分隔，表示测试点的数据。 接下来 $q$ 行，每行两个整数 $u_i,\ l_i$ ($1\le u_i \le 1.8\times 10^7,\ 1\le l_i\le n$)，用单个空格分隔，表示一次询问。

对每个询问输出一行两个数，即对应询问的最大得分和以及能获得该得分的最小 $r_i$ ($l_i\le r_i\le n$)，用单个空格分隔。

10 7
10 9 2 1 5 3 10 10 1 8
14 4
17 5
13 10
16 1
12 4
16 6
16 3

55 6
60 6
-68 10
-58 6
41 6
20 6
79 6

6 8
3 7 7 10 8 9
21 1
20 4
21 3
21 5
21 1
21 2
21 2
21 5

170 3
-100 4
70 3
-27 6
170 3
140 3
140 3
-27 6

在样例 1 的第一个询问中，$u_1=14,\ l_1=4$。若我们选择 $r_1=6$，则最后的得分和为 $\sum_{i=1}^{10^6}{score(i,4,6)}$。其中： - $score(1,4,6)=13+9+11=33$； - $score(2,4,6)=0+14+14=28$； - $score(3,4,6)=0+14-9=5$； - $score(4,4,6)=0+14+0=14$； - $score(5,4,6)=0-25+0=-25$； - $i$ 取其他值时均有 $score(i,4,6)=0+0+0=0$。 故 $r_1=6$ 时得分和为 $33+28+5+14-25=55$。 可以证明在 $r_1$ 取其他值时无法得到更大的得分和，故答案为 $55$，且能达成的最小 $r_1$ 为 $6$。