(より詳しい解説は後日ブログで公開します)

\(g(n) := \displaystyle\sum_{m=1}^n f(m)^A\) とします．

\(g(n)\) は包除原理によって，素数 \(p_1 < \cdots < p_l\) を決め打ったとき，\(n\) 以下の \(p_1^2 \cdots p_l^2\) の倍数の個数に，\(l\) に応じた適切な重みをかけたものを合計する，という形で求まります．「適切な重み」は \(0^A, 1^A, \ldots\) から定まり，考えるべき \(l\) は非常に小さいので事前に計算できます (実際には，第 2 種 Stirling 数によって \(l! S(A, l)\) と書けます)．

求めたい \(g(n)\) は \(g(\lfloor N/z \rfloor)\) という形ですが，\(g(\lfloor N/z \rfloor) = \displaystyle\sum_{x^2 y z \le N} \mathrm{weight}(x)\) というように書けます．

\(x \le N^{1/2}\) は列挙できます (オーダーは変わりませんが， square-free な \(x\) のみ見ればよいです)．そして \(y, z\) の大小によって以下の方法を使い分けます：

• \(y \le z\) については，\(y\) を列挙すると，\(z\) のある範囲について足し込むという形になります．これは差分を管理しておけばよいです．
• \(y > z\) については，\(z\) を列挙すると，\(\sum_y 1\) は簡単に求まります．

これにより時間計算量 \(O\left( \sum_x (N/x^2)^{1/2} \right) = O(N^{1/2} \log(N))\) を達成できます．

なおこの問題は，\(p^e \mapsto \begin{cases} 1 & (e=1) \\ \exp(X) & (e \ge 2) \end{cases}\) なる乗法的関数の \([X^A/A!]\) を見ていると考えるとわかりやすいかもしれません．