\(T\)组询问，每组给定\(n,k\)，求\(\sum\limits_{i=1}^n \sigma_0(i^k)\)（\(T\le 10^4\)，\(n,k\le 10^7\)）
将\(m\)表示成\(m=\prod\limits_{i=1}^c p_i^{\alpha_i}\)，则\(\sigma_0(m)=\prod\limits_{i=1}^c(\alpha_i+1)\)，则\(\sigma_0(m^k)=\prod\limits_{i=1}^c (k\cdot \alpha_i+1)\)
\(\sigma(m^k)\)是个关于\(k\)的\(c\)次多项式（\(c\le 8\)）
可以线性筛出\(i\in[1,n]\)的多项式系数，再求前缀和
令\(w(i)\)为\(i\)的质因数个数
\(\sum\limits_{i=1}^n \sigma_0(i^k)=\sum\limits_{i=1}^n k^{w(i)}\frac{n}{i}\)
解释一下：
\(d=\prod\limits_{i=1}^c p_i^{\alpha_i}\)
将每个约数映射为\(g(d)=\prod\limits_{i=1}^c p_i^{\frac{\alpha_i}{k}}\)
\(g(d)|i\)等价于\(d|i^k\)，对于给定的\(d\)，可以找到\(\frac{n}{g(d)}\)个数字使得\(d|i^k\)
\(\sum\limits_{i=1}^n \sigma_0(i^k)=\sum\limits_{d=1}^{n^k}\frac{n}{g(d)}\)
枚举\(i=g(d)\)，显然有\(k^{w(i)}\)个\(d\)满足\(g(d)=i\)
原文：https://www.cnblogs.com/Grice/p/12932852.html