ABC179 C問題 A x B + C を解く

ABC179 C問題 A x B + C が解けなかったので、反省しながら振り返ります。

atcoder.jp

正整数 N が与えられます。 A \times B + C = N を満たす正整数の組 (A, B, C)はいくつありますか？

Nの範囲は 2 \leq N \leq 10^6です。
最初私は式を変形して、 A \times B = N - Cなので、Cを1からN-1までループして、約数の組み合わせ出せば良いと思いました。
もちろんこの目論見はハズレて、約数を求めるのにも O(\sqrt{N})かかり、さらにCを1からN-1までループするので、最大で 10^{9}になりそう。

ここで方針が立たず、時間もかかったので、ギブアップしました。

解説を読んで、正の整数という条件から単純な問題に帰結できることを理解しました。。。

まず、 A \times B \leq N - 1という条件に気づけませんでした。
A \times B + Cを考えた時に、正の整数の組み合わせという条件からCの値は最小でも1になります。

A \times B \leq N - 1の条件で探索するとAとBの2つあるので、 O(N^2)という計算になってしまいます

Aをループさせて、 A \times B \leq N - 1を満たすBの個数を求めます。
例えば、 5 \times B \leq 100だとすると、これを満たすBの個数は 100 / 5になります。

なので、コードにすると以下のようになります。

N = int(input())
ans = 0
for i in range(1, N):
    ans += (N - 1) // i
print(ans)

うーん、気づけなかったなぁ。気づけるようになる日は来るのだろうか。慣れの問題なのだろうか。。。