はじめに
$O(K ^ \frac{2}{3} (\log \log K) ^ \frac{1}{3} + K ^ \frac{1}{2} \log N)$ 解法を解説します。
解法
過程を色々すっ飛ばすと、答えは式 $(1)$ で計算されることが分かります。ここで、$\varphi$ は オイラーの $\varphi$ 関数 です。
$$ \sum _ {i = 1} ^ K \varphi(i) \cdot\left\lfloor\dfrac{K}{i}\right\rfloor ^ N \tag{1} $$
この式にたどり着くまでの考察などは以下の記事で解説されていますので、そちらを参照してください。
さて、式 $(1)$ に現れる $\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor$ について、$i$ を正整数全体で動かしたときに高々 $O(\sqrt{K})$ 種類の値しか取らないことが知られています。
証明
まず、$1\leq i \leq \sqrt{K}$ に対して、ありうる $\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor$ の値は高々 $\lfloor \sqrt{K}\rfloor$ 種類です。
また、$\sqrt{K}\lt i$ に対しては、$\dfrac{K}{i}\lt \sqrt{K}$ が成り立つのでありうる $\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor$ の値は高々 $\lfloor \sqrt{K}\rfloor$ 種類です。
以上より、$i$ が正整数全体を動くとき、$\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor$ が取り得る値の種類は高々 $2\lfloor\sqrt{K}\rfloor=O(\sqrt{K})$ 通りであることが示されました。(証明終)
そこで、式 $(1)$ の和を $\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor$ の値ごとにまとめて計算することを考えます。$\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor$ が取り得る値の集合を $S$、正整数 $q\in S$ に対して $\displaystyle \left\lfloor\dfrac{K}{i}\right\rfloor = q$ となる正整数 $i$ の集合を $S _ q$ とします。
$$ \begin{aligned} i \in S _ q &\iff q \leq \dfrac{K}{i} \lt q + 1 \land i \in \N^+ \\ &\iff \dfrac{K}{q+1}\lt i \leq \dfrac{K}{q} \land i \in \N^+ \\ &\iff \left\lfloor\dfrac{K}{q+1}\right\rfloor \lt i \leq \left\lfloor\dfrac{K}{q} \right\rfloor \land i \in \N^+ \end{aligned} $$
より、$\displaystyle f(q) := \sum _ {i = 1} ^ {\lfloor K/q \rfloor} \varphi(i)$ と定義すれば、式 $(1)$ は次の式 $(2)$ のように書き換えられます。
$$ \sum _ {q \in S} (f(q) - f(q + 1)) \cdot q ^ N \tag{2} $$
$f(\cdot)$ が $O(1)$ で取得できると仮定すれば、$|S| = O(K ^ \frac{1}{2})$ より式 $(2)$ は $O(K ^ \frac{1}{2} \log N)$ で計算することが出来ます。
実は、$f(q)$ は以下の記事で解説されているアルゴリズムにより $O(K ^ \frac{2}{3} (\log \log K) ^ \frac{1}{3})$ で全て前計算することが出来ます。
以上より、本問を全体 $O(K ^ \frac{2}{3} (\log \log K) ^ \frac{1}{3} + K ^ \frac{1}{2} \log N)$ で解くことが出来ました。
実装
おわりに
独自要素が一切無くて、これで良いのかという気はする。
