これ、一見すると $O(N^{\frac{1}{3} + \frac{1}{2}}) = O(N^{\frac{5}{6}})$ の計算量が必要に思えてしまうね！
問題へのリンク

問題概要

正の整数 $N$ が与えられる。

$A \le B \le C$ かつ $ABC \le N$ であるような正の整数の組 $(A, B, C)$ の個数を求めよ。

制約

$1 \le N \le 10^{11}$

$A$ の範囲を絞る

約数列挙アルゴリズムなどでもお馴染みの、大小関係から整数の範囲を絞って探索する系！！

まず、 $A \le B \le C$ かつ $ABC \le N$ から、次のことが言える。

$N \ge ABC \ge A^{3}$ より、 $A \le N^{\frac{1}{3}}$

直観的には、 $A, B, C$ の 3 人で $N$ を 3 分割するとき、 $A$ の分が一番少ないから、 $A$ の分は $N^{\frac{1}{3}}$ 以下になるよね......という感じ！

よって、for 文を回して探索するときに、 $A = 1, 2, \dots, N^{\frac{1}{3}}$ の範囲を調べれば良いことがわかった。実装するときには、次のように書くとよい！！

for (long long A = 1; A * A * A <= N; ++A) {

}

この書き方のメリットは、A <= pow(N, 1.0/3) などと書くのに比べて、数値誤差の心配もない。

$B$ の範囲を絞る

さて、次は $A$ が固定して考えよう。このとき、 $ABC \le N$ いう式において、 $A$ はもはや定数なので、次のように式変形しておく。

$BC \le \displaystyle \frac{N}{A}$

さらに $B \le C$ より、次のことが言える。

$\displaystyle \frac{N}{A} \ge BC \ge B^{2}$ より、 $B \le \bigl(\displaystyle \frac{N}{A}\bigr)^{\frac{1}{2}}$

よって、for 文を回して探索するときに、 $B = 1, 2, \dots, \bigl(\displaystyle \frac{N}{A}\bigr)^{\frac{1}{2}}$ の範囲を調べれば良いことがわかった。実装するときには、次のように書くとよい！！

for (long long A = 1; A * A * A <= N; ++A) {
    for (long long B = A; A * B * B <= N; ++B) {

    }
}

$C$ の個数

最後に、 $A, B$ を決めた上で $C$ の個数は次のように求められる。

$C \ge B$ である
$ABC \le N$ より、 $C \le \displaystyle \frac{N}{AB}$ である

これらのことから、 $C$ は $B$ 以上 $\displaystyle \frac{N}{AB}$ 以下の整数なので

$\displaystyle \frac{N}{AB} - B + 1$ 個

ある。

コード

以上の解法は次のように実装できる。計算量については後で考える。

なお、コンテスト中に、この解法の計算量が大丈夫か不安になった人も多いと思う。心配ならば、入力例 3 ( $N = 100000000000$ ) が制約範囲内での最大ケースになっているので、それを試すのがよさそうである。このケースで十分高速なら大丈夫！

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    
    long long res = 0;
    for (long long A = 1; A * A * A <= N; ++A) {
        for (long long B = A; A * B * B <= N; ++B) {
            res += N / (A * B) - B + 1;
        }
    }
    cout << res << endl;
}

計算量

$A, B$ の動く範囲を整理すると、次のようになる。

$A \le N^{\frac{1}{3}}$
$B \le \bigl(\displaystyle \frac{N}{A}\bigr)^{\frac{1}{2}}$

2 個目の $B$ について、 $A \ge 1$ より、

$B \le N^{\frac{1}{2}}$

となるので、 $(A, B)$ の探索には $O(N^{\frac{1}{3} + \frac{1}{2}}) = O(N^{\frac{5}{6}})$ という計算量が必要な気がしてしまう。もし本当にそうなら、 $N \le 10^{11}$ では間に合わない。

しかし実は、上記条件を満たす $(A, B)$ の組の個数は $O(N^{\frac{2}{3}})$ と評価できることが示せる。editorial に詳細解説がある。

atcoder.jp

直観的には、 $ABC \le N$ という式において、3 変数のうち 2 変数を動かして考えているのだから、 $O(N^{\frac{2}{3}})$ になるんだな......と理解することにする。 $ABCD \le N$ となる $A, B, C, D$ の探索も同様に $O(N^{\frac{3}{4}})$ の計算量となるだろう。