33OJ
登录 注册

#P17517. [ECUSTPC 2026 Fall] 根除

[ECUSTPC 2026 Fall] 根除

背景

我们终于等来了黎明,可这座城的根除了记得黑夜,似乎什么也没能留下。

题目描述

我们通常会把一个较大的数字的开根分解为最简的根式,例如 432=123\sqrt{432} = 12 \sqrt3。

在 N\mathbb{N} 上定义数论函数 $f(n) = \min\{a \mid n = ab^2, a, b \in \mathbb{N}\}$,即函数值为满足等式的最小自然数 aa,可以发现这样的 aa 总是存在的。

给定 qq 次询问,每次询问给定 l,rl, r,请分别求出 ∑i=lrf(i)\sum_{i=l}^r f(i) 的答案在模 998 244 353998\,244\,353 下的值。

输入格式

第一行输入一个整数 qq (1≤q≤5001 \le q \le 500),表示询问的数量。

随后输入 qq 行两个整数 ll 和 rr (1≤l≤r≤10121 \le l \le r \le 10^{12}),表示一次询问的区间。

输出格式

对于每次询问,输出一行一个整数,表示 ∑i=lrf(i)\sum_{i=l}^r f(i) 在模 998 244 353998\,244\,353 下的值。

4
432 432
1 10
10 15
1 100000000
3
38
66
651260790

提示

样例 1 解释

对于第 2 次和第 3 次询问,对应的 ff 值为:

$$\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.$$