#P17517. [ECUSTPC 2026 Fall] 根除
[ECUSTPC 2026 Fall] 根除
背景
我们终于等来了黎明,可这座城的根除了记得黑夜,似乎什么也没能留下。
题目描述
我们通常会把一个较大的数字的开根分解为最简的根式,例如 。
在 上定义数论函数 $f(n) = \min\{a \mid n = ab^2, a, b \in \mathbb{N}\}$,即函数值为满足等式的最小自然数 ,可以发现这样的 总是存在的。
给定 次询问,每次询问给定 ,请分别求出 的答案在模 下的值。
输入格式
第一行输入一个整数 (),表示询问的数量。
随后输入 行两个整数 和 (),表示一次询问的区间。
输出格式
对于每次询问,输出一行一个整数,表示 在模 下的值。
4
432 432
1 10
10 15
1 100000000
3
38
66
651260790
提示
样例 1 解释
对于第 2 次和第 3 次询问,对应的 值为:
$$\begin{array}{c|ccccccccccccccc} n &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ \hline f(n) &1&2&3&1&5&6&7&2&1&10&11&3&13&14&15 \end{array}$$其中第 3 次询问即为
$$\sum_{i = 10}^{15}f(i) = f(10) + f(11) + f(12) + f(13) + f(14) + f(15) = 10 + 11 + 3 + 13 + 14 + 15 = 66.$$