キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) C - ABC conjecture (Python)

お久しぶりです！

久々に解説記事を書きたいと思います！

問題はこちら！
https://atcoder.jp/contests/abc227/tasks/abc227_c

数学問題なので得意分野だし解説しようかと思いま〜す

1. 問題の概要
2. 制約と入力例
- 2-1. 制約
- 2-2. 入力例
  - 入力例１
  - 入力例２
3. 見てすぐに考えたこと
4. 解説
5. ACコード
6. 最後に

1. 問題の概要

$\displaystyle A \leqq B \leqq C かつ ABC \leqq N を満たす自然数 (A, B, C) の個数を求めよ。 \\ 答えは2^{63}未満であることが保証されます。$

2. 制約と入力例

2-1. 制約

$\displaystyle 1 \leqq N \leqq 10^{11}$
$\displaystyle N は整数$

2-2. 入力例

入力例１

N = 4 のとき、条件を満たす組み合わせは、
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2) の５つです。

入力例２

N = 100000000000 のとき、条件を満たす組み合わせは、 5745290566750 個です。

3. 見てすぐに考えたこと

入力例２からわかるように N が最大の時の個数がとても多いので単純に回すのは絶対に無理
整数問題でよくある O(N^2) 解法でもTLEしてしまう。
高校数学の整数問題 $\displaystyle \frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1 を満たす自然数 (x, y, z) の個数を求めよ。$ に似ている？

ということで、３つ目の直感で思ったことから不等式で条件を絞っていこうと考えました。

4. 解説

まずは与えられた不等式を用いて範囲を絞ります！

$\displaystyle A \times A \times A \leqq ABC \leqq N \\ A^3 \leqq N \\ A \leqq N^\frac{1}{3}$

とわかるので、探索するAの範囲は $\displaystyle N^{\frac{1}{3}}$ までで良いことがわかります。

次にBの範囲を絞っていきます。

$\displaystyle BC \leqq \frac{N}{A} \\ B \times B \leqq BC \leqq \frac{N}{A} \\ B^2 \leqq \frac{N}{A} \\ B \leqq \sqrt{\frac{N}{A}}$

したがって、探索するBの範囲は $\displaystyle \sqrt{\frac{N}{A}}$ までで良いことがわかります。

ここまで、範囲が絞れたらあとは条件を満たす $\displaystyle C \leqq \sqrt{\frac{N}{AB}}$ を満たす C の個数を求めれば良いです！

5. ACコード

n = int(input())

ans = 0
for a in range(1, int(n ** (1 / 3)) + 10):
    for b in range(a, int((n / a) ** 0.5) + 10):
        ans += max(0, int(n // (a * b)) - b + 1)

print(ans)