AtCoder-ABC179 C - A x B + C【Python解答例】

AtCoderの練習としてAtCoder Beginner Contest179の問題C　A x B + Cに取り組みました。
atcoder.jp

AtCoder Beginner Contest179 C - A x B + C

問題文

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

制約

2≤N≤10^6
入力はすべて整数

解答例

# coding:utf-8

n = int(input())

count = 0

for i in range(n):
    if i == 0:
        count += n - 1
    elif i == n:
        count += 0
    elif n % (i + 1) != 0:
        count += n // (i + 1)
    else:
        count += n // (i + 1) - 1

print(count)

解説

問題文からA×BがNより小さい値なら必ずCは存在するといえます。
なので、Nより小さいAとBの組み合わせが何個あるかを求めればいいと思います。

AとBの組み合わせの数は、AとBの2重ループで簡単に求まりそうですが、
時間切れになると思ったので試していません。
（詳しい説明ができないです…勉強不足）

例えばN＝10、A＝3のときに条件にあてはまるBは1～3となります。
(A,B,C)=(3,1,7),(3,2,4),(3,3,1)
つまりNをAで割ったときの商の数が求める条件を満たすので、
その商を足し合わせていって答えを求めました。
4種類　条件分けとして、
①A=1の場合：(A,B)=(N,1)のときCが存在しないので、Nから1を引いた数を足しました。
②A＝Nの場合：①と同じ理由から、条件にあう組み合わせがありません。
③AでNが割り切れない場合：NをAで割ったときの商を足しています。
④AでNが割り切れる場合：例えばN=10、A＝2の場合、(A,B)=(2,5)ではCが存在しないので、NをAで割った商から1を引いています。

もっとシンプルに求めることもできるかもしれませんので、
ほかの方の解法など勉強したいと思います。