ある数論的関数の和

$f(n)$ の特徴

$p, q$ を素数とします。そうすると、 $e\ge 1$ に対して $f(p^e)=f(q^e)$ が成り立ちます。

もっと一般に、正整数 $n, m$ に対して $n, m$ の素因数分解をそれぞれ $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, m=q_1^{\beta_1}q_2^{\beta_2}\cdots q_l^{\beta_l}$、ただし $p_i,q_i$ は素数、 $\alpha_i,\beta_i\ge 1$ とすると、多重集合 $\{\alpha_1, \alpha_2, \cdots, \alpha_k\}$ と $\{\beta_1, \beta_2, \cdots, \beta_l\}$ が一致していれば $f(n)=f(m)$ が言えます。

つまり、素因数の指数の多重集合によって、 $f(n)$ の値が決定されるということです。以降は $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ に対して、多重集合 $\{\alpha_1, \alpha_2, \cdots, \alpha_k\}$ を $n$ の Prime Signature ( https://en.wikipedia.org/wiki/Prime_signature )と呼ぶことにします。

$N$ 以下の Prime Signature は何種類あるか？

$N$ 以下の Prime Signature は何種類あるでしょうか？ $N=10^9$ の場合、素因数の個数は $29$ 以下であるため、 $29$ 以下の分割数の和で個数が評価できます。A000070 によると、 $23000$ 個程度です。しかし、実際はより少なく、次のようになります。

下の表の2べき版については https://oeis.org/A025488 にあります。

Prime Signature を列挙し、それぞれについて $f$ を求めることが比較的短時間で出来ます。

最後に Lucy DP + Black Algorithm

各 Prime Signature についてその $f$ の値が分かったとします。

この問題に答えるために、各 Prime Signature について $N$ 以下でその Prime Signature になるようなものの個数をすべて求めたいです。

まず、いわゆる Lucy DP によって各 $k=\lfloor N/i \rfloor$ に対して $k$ 以下の素数の個数を $O(N^{2/3})$ から $O(N^{3/4})$ 時間で求めます。

そこから、 Black Algorithm を応用した DFS を適用します。次の $N$ 頂点の木を考えます。

• 頂点の番号は $1$ から $N$ までである。
• 頂点 $1$ は根であり、頂点 $n$ $(n\ge 2)$ の親は、 $n/\mathrm{gpf}(n)$ である。ただし、 $\mathrm{gpf}(n)$ は $n$ の素因数のうち最大のものとする。

これを DFS しますが、葉であるような頂点は探索しないことにします。探索回数は次の表の通りになります。

よって、競プロで使う範囲の $N$ に対しては $O(N^{2/3})$ や $O(N^{3/4})$ と同じくらいと見積もることができます。ただし、実際は $O(N^{1-\varepsilon})$ らしいです。（ABC370-G の解説）

ここで、葉でない頂点 $n$ について、そこからつながる $n \times \mathrm{gpf}(n)$ 以外の葉はすべて Prime Signature が同じになっています。よって、各 $\lfloor N/i \rfloor$ 以下の素数の個数を数え上げたことによって、 各 Prime Signature となる $N$ 以下の正整数の個数を探索回数の定数倍で求めることができます。

以上を実装することでこの問題に答えることができます。