公式解説

aac003_g 解説

約数の問題に有用な関数として、メビウス関数（ここでは、$\mu(n)$）があり、以下が成り立ちます。
$n$ を素因数分解して $n = \prod {p_i}^{e_i}$ としたとき、素因数の個数を $m$ として

なお、$\mu(1) = 1$ となります。
これを用いると、次が成り立ちます。

最後の変形は、

となることから成り立ちます。
（$\mu(d)$ と $\mu(n/d)$ が通常 $1$ と $-1$ になって打ち消しあう、というイメージです）

よって、

を得ました。

あとは、

のように「配る DP」の形で計算することで、計算量を $\mathcal O(\frac N1 + \frac N2 + \cdots + \frac N N) = \mathcal O(N \log N)$ に抑えることが出来ました。