2019 银川 D 原题强化为
\sum_{S} f(S)^k
原式
\begin{aligned}
&=\sum_{a_1}\sum_{a_2}\sum_{a_3} ... \sum_{a_n}(\prod_{i}^na_i)^k\\
&=\sum_{d=1}^md^{kn}\sum_{a_1}^{u=\lfloor\frac{m}{d}\rfloor}\sum_{a_2}^u\sum_{a_3}^u ... \sum_{a_n}^u(\prod_{i}^na_i)^k[\gcd(a_1,a_2,...,a_n)=1]\\
&=\sum_{d=1}^md^{kn}\sum_{e=1}^{u} \mu(e)e^{kn}\sum_{a_1}^{u=\lfloor\frac{m}{de}\rfloor}\sum_{a_2}^u\sum_{a_3}^u ... \sum_{a_n}^u(\prod_{i}^na_i)^k\\
\end{aligned}
令 \begin{aligned}S_i = \sum_{j=1}^i j^k\end{aligned} ，则 \begin{aligned}\sum_{a_1}^{u=\lfloor\frac{m}{de}\rfloor}\sum_{a_2}^u\sum_{a_3}^u ... \sum_{a_n}^u(\prod_{i}^na_i)^k = (S_{\left\lfloor \frac{m}{de}\right\rfloor})^n \end{aligned}
同时令 \begin{aligned}f(d)=\mu(d)d^{kn}, g(d)=d^{kn}\end{aligned}
原式
\begin{aligned}
&=\sum_{d=1}^md^{kn}\sum_{e=1}^{u} \mu(e)e^{kn}\sum_{a_1}^{u=\lfloor\frac{m}{de}\rfloor}\sum_{a_2}^u\sum_{a_3}^u ... \sum_{a_n}^u(\prod_{i}^na_i)^k\\
&=\sum_{T=de=1}^m (S_{\left\lfloor \frac{m}{T}\right\rfloor})^n\sum_{d|T}f(d)g(\frac{T}{d})
\end{aligned}
因为模数比较特殊并且 n 比较大 并且模数非质数，所以需要用一下 ex欧拉定理，然后直接粗合理调和级数分块询问即可。