AtCoder Beginner Contest 179 [ C - A x B + C ]をPythonで解く(300点、⬜️灰色diff)
問題
正整数Nが与えられます。A x B + C = Nを満たす正整数の組 (A,B,C)はいくつありますか?
atcoder.jp
制約
- 2 ≤ N ≤ 106
- 入力はすべて整数
解法
A, B, C はすべて1以上。
A x B + C = N
この式を展開していく。
C = N - A x B
Cは1以上なので
1 ≤ N - A x B
A x B ≤ N - 1
ゆえにA x Bの組み合わせ数が答え。
仮にA = 3、N=101とすると
3 x B ≤ 100
とすると
1 ≤ B ≤ 33
つまり100/3でBの数は求められる。
あとはAを総当たりで回してカウントすれば良い。 ゆえに答えは