{"problem":{"name":"[SNCPC2024] 猜质数 II","description":{"content":"为了悄悄准备一个神秘的质数，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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10700"},"statements":[{"statement_type":"Markdown","content":"为了悄悄准备一个神秘的质数，MCPlayer542 伤透了脑筋。\n\n随后他发明了一种~~聪明~~愚蠢的办法，并起名为“质数分”。\n\n他准备了 $n$ 个不同的数 $a_1,\\ a_2,\\ \\ldots,\\ a_n$ 作为测试点，并定义“质数分” $score(x,l,r)$ 如下：\n\n$$score(x,l,r)=\\sum_{i=l}^r{f(x,a_i)}$$\n其中\n$$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.$$\n\n可见质数的“质数分”通常会比较高~~但还是没什么卵用~~。\n\n于是 MCPlayer542 急了，现在他只想暴力乱测，并得到一个得分和 $\\sum_{i=1}^{10^6}{score(i,l,r)}$。他打算测试 $q$ 次，每次测试给定 $u$ 和 $l$，其中 $u$ 为函数 $f(x,y)$ 的参数。\n\n对于每次询问，他想知道所能得到的最大得分和以及能得到这个最大得分和的最小 $r$ 是多少。\n\n## Input\n\n输入数据的第一行包含两个整数 $n,\\ q$ ($1\\le n,\\ q\\le 5\\times 10^5$)，用单个空格分隔。\n\n第二行包含 $n$ 个整数 $a_1,\\ a_2,\\ \\ldots,\\ a_n$ ($1\\le a_i\\le 10^6$)，用单个空格分隔，表示测试点的数据。\n\n接下来 $q$ 行，每行两个整数 $u_i,\\ l_i$ ($1\\le u_i \\le 1.8\\times 10^7,\\ 1\\le l_i\\le n$)，用单个空格分隔，表示一次询问。\n\n## Output\n\n对每个询问输出一行两个数，即对应询问的最大得分和以及能获得该得分的最小 $r_i$ ($l_i\\le r_i\\le n$)，用单个空格分隔。\n\n[samples]\n\n## Note\n\n在样例 1 的第一个询问中，$u_1=14,\\ l_1=4$。若我们选择 $r_1=6$，则最后的得分和为 $\\sum_{i=1}^{10^6}{score(i,4,6)}$。其中：\n- $score(1,4,6)=13+9+11=33$；\n- $score(2,4,6)=0+14+14=28$；\n- $score(3,4,6)=0+14-9=5$；\n- $score(4,4,6)=0+14+0=14$；\n- $score(5,4,6)=0-25+0=-25$；\n- $i$ 取其他值时均有 $score(i,4,6)=0+0+0=0$。\n\n故 $r_1=6$ 时得分和为 $33+28+5+14-25=55$。\n\n可以证明在 $r_1$ 取其他值时无法得到更大的得分和，故答案为 $55$，且能达成的最小 $r_1$ 为 $6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10700","tags":["2024","O2优化","陕西","省赛/邀请赛"],"sample_group":[["10 7\n10 9 2 1 5 3 10 10 1 8\n14 4\n17 5\n13 10\n16 1\n12 4\n16 6\n16 3\n","55 6\n60 6\n-68 10\n-58 6\n41 6\n20 6\n79 6\n"],["6 8\n3 7 7 10 8 9\n21 1\n20 4\n21 3\n21 5\n21 1\n21 2\n21 2\n21 5\n","170 3\n-100 4\n70 3\n-27 6\n170 3\n140 3\n140 3\n-27 6\n"]],"created_at":"2026-03-03 11:09:25"}}