原案者でした。原案者としての想定解を紹介します。(この解法は計算量の見積もりが公式解説より容易だと思います。)

まず、重要な観察として、\(a\) と \(b\) の最大値を見積もります。すると

\[a^5 \leq a^2 b c^2 \leq N \to a \leq N^{1/5}\]

\[b^3 \leq b c^2 \leq N \to b \leq N^{1/3}\]

より、(\(a \lt b\) の条件も合わせると) \(a \leq N^{1/5}, a \lt b \leq N^{1/3}\) の範囲に含まれる素数の組のみを調べればよいわかります。よって、\(a, b\) を全探索しても \(N^{8/15}\) 回 (\(N = 10^{12}\) のときは \(10^{6.4}\) 回) 以下の探索で済むことが分かります。

\(a, b\) を固定した場合を考えます。このときの \(c\) としてあり得る値は、

\[a^2 b c^2 \leq N \to c \leq \sqrt{\dfrac{N}{a^2b}}\]

より、

• \(b\) より大きく、\(\sqrt{\dfrac{N}{a^2 b}}\) 以下である素数

であるとわかります。(以降では見やすさのため \(\sqrt{\dfrac{N}{a^2 b}}\) を \(D\) とおきます。)

ここで \(S(n)\) を

• \(S(n) =\) (\(n\) 以下の素数の個数)

と定義すると、条件を満たすような \(c\) の個数は

• \(b \leq D\)のとき : \(S(D) - S(b)\) 個
• \(b \gt D\) のとき : \(0\) 個

であり、また、\(D \leq \sqrt{N} (\leq 10^6)\) です。よって、あらかじめ \(\sqrt{N}\) 以下の素数を列挙して、その後 \(S(1), S(2), \dots, S(\sqrt{N})\) を累積和を利用して前計算しておけば、\(a, b\) を固定したときの \(c\) の個数を \(\mathrm{O}(1)\) で計算できます。

以上よりこの問題を \(\mathrm{O}(N^{8/15})\) で解くことができました。詳しいアルゴリズムは実装例をご参考ください。

• 実装例 (Python)

from math import isqrt

N = int(input())

# sqrt(N) 以下の素数の列挙
sieve = [1] * (isqrt(N) + 1)
primes = []
for p in range(2, len(sieve)):
  if sieve[p] == 0:
    continue
  primes.append(p)
  for j in range(p * p, len(sieve), p):
    sieve[j] = 0

# prefix_sum[n] : (n 以下の素数の個数) 
prefix_sum = sieve
for i in range(len(prefix_sum) - 1):
  prefix_sum[i + 1] += prefix_sum[i]

ans = 0

# a, b を全探索する
for i in range(len(primes)):
  a = primes[i]
  if a * a * a * a * a >= N:
    break
  for j in range(i + 1, len(primes)):
    b = primes[j]
    if a * a * b * b * b >= N:
      break
    ans += prefix_sum[isqrt(N // (a * a * b))] - prefix_sum[b]
print(ans)