P6060 [加油武汉] 传染病研究

在得知 W 市爆发的肺炎之后，科学家们立刻投入了紧锣密鼓的研究之中。 （下面的部分非严谨科学，大家做题以外切勿当真） 假设某种病毒在第 $x$ 天的传播能力为 $D(x)$，该函数的含义为 $x$ 的约数个数。例如 $D(6)=4, D(7)=2$。 现在给定你总的传播天数 $n$ 和一个影响常数 $k$，你需要计算 $\sum_{i=1}^n D(i^k)$ 也就是 $D(1^k)+D(2^k)+D(3^k)+ \cdots +D(n^k) $。 由于答案可能很大，请对 $998244353$ 取模。

无

无

- 对于 $20\%$ 的数据，满足 $1\leq T\leq 10,1\leq n\leq 100,1\leq k\leq 6$； - 存在另外 $30\%$ 的数据，满足 $1 \leq T \leq 10^4, 1\leq n \leq 10^7,k=1$； - 对于 $100\%$ 的数据，满足 $1 \leq T \leq 10^4, 1\leq n,k \leq 10^7$。 【样例解释】 $D(1^2)+D(2^2)+D(3^2)+D(4^2)+D(5^2)$ $=D(1)+D(4)+D(9)+D(16)+D(25)$ $=(1)+(3)+(3)+(5)+(3)$ 1 有约数 1 个：1； 4 有约数 3 个：1，2，4； 9 有约数 3 个：1，3，9； 16 有约数 5 个：1，2，4，8，16； 25 有约数 3 个：1，5，25； 一共有15个