【AtCoder】abc179 C - A x B + C

解説動画を見ながら自分なりに噛み砕いたメモ。

A * B + C = N

式変形するとこうなる。

C = N - A * B

つまり、CはAとBが決まれば自動的に決まる。

なのでAとBの組み合わせだけを考えれば良いという状態に持っていきたい。
A * Bの範囲を確定させたいので、Cの値について考える。
まずCの値が0の場合、これはNG。
A, B, Cいずれも正整数という制約があり、0は正整数ではないから。
なのでCに入り得る最小の値は1なので、これを最初の式に代入すると、

A * B + 1 = N
A * B = N - 1

よって、

1 <= A * B <= N - 1

がいえる。
(ちなみに、Cは 1 <= C <= N - 1 )

ここでAに最小の正整数1を代入してみる。

1 <= 1 * B <= N - 1

この場合は、Bの範囲は

1 <= B <= N - 1

になる。

続いてA = 2の場合。

1 <= 2 * B <= N - 1

だから、Bの範囲は

1 <= B <= (N - 1) / 2

となる。
これはNにも具体的な数値を代入して考えてみるとわかりやすい。
もし N = 10 の場合、

1 <= 2 * B <= 10 - 1
1 <= 2 * B <= 9

となり、Bの範囲は 9 / 2 の商の小数点切り捨てが最大となるのがわかるはず。

1 <= B <= 9 / 2
1 <= B <= 4

考察の材料が揃ってきたので、AにもBにも代入せずに考えると、

1 <= A * B <= N - 1

Bについて、

1 <= B <= (N - 1) / 2

と一般化できる。

あとは、Aが取り得る全ての値について考え、合算すると答えになる。
Aの範囲は

1 <= A <= N - 1

なので、コードは下記のようになる。

#include <iostream>

typedef long long ll;

int main() {
    ll n;
    cin >> n;

    auto res = 0;
    for (auto a = 1; a <= n - 1; a++) {
        res += (n - 1) / a;
    }

    cout << res << endl;
    return 0;
}