ABC179 C - A x B + C 解法メモ

はじめに

今日の見直し問題は ABC179 C - A x B + C です。

問題URL: https://atcoder.jp/contests/abc179/tasks/abc179_c
解説URL: https://atcoder.jp/contests/abc179/tasks/abc179_c/editorial

問題文

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

制約

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

step 1: A, B, C がとりえる値の範囲

$A$、$B$、$C$ がとりえる値の範囲を考えます。

まず、問題文に正整数とあるので、$1 \leq A$、$1 \leq B$、$1 \leq C$ であることが条件です。
$A = 1$、$B = 1$、$C = 1$ のとき、$N = 2$ となるので、制約を満たします。

次に、$A$、$B$、$C$ の上限値を考えます。
$C$ が最小（ $C = 1$ ）のときに $A$ または $B$ が上限値をとることができ、その上限値 $A_{max}$ 、 $B_{max}$ は

$$
A_{max} = N - 1\\
B_{max} = N - 1
$$

です。
また、$A$ 、 $B$ がともに最小（ $A = 1$ かつ $B = 1$ ）のときに $C$ が上限値をとることができ、その上限値 $C_{max}$ は

$$
C_{max} = N - 1
$$

です。

以上より、$A$、$B$、$C$ がとりえる値の範囲は、

• $1 \leq A \leq N - 1$
• $1 \leq B \leq N - 1$
• $1 \leq C \leq N - 1$

であることがわかります。

step 2: 単純な解法

単純な解法として全探索を考えてみます。

int getABCCombinationsCount(int N) {
    int ABCCombinationsCount = 0;
    for(int a = 1; a < N; a++) {
        for(int b = 1; b < N; b++) {
            for(int c = 1; c < N; c++) {
                if(a * b + c == N) {
                    ABCCombinationsCount++;
                }
            }
        }
    }
    return ABCCombinationsCount;
}

全探索で $A \times B + C = N$ を満たす正整数の組 $(A, B, C)$ の数を計算する関数 getABCCombinationsCount() を考えてみました。
時間計算量は $O(N^3)$ です。
$N$ は最大で $10^6$ なので、実行時間が制限に間に合いません。

step 3: 改良アプローチ

別のアプローチを考えてみます。

条件式 $A \times B + C = N$ を変形してみます。

\begin{align}
&A \times B + C = N\\\\
&\Leftrightarrow A \times B = N - C\\\\
\end{align}

最終行の等式の右辺がとりえる値の範囲は、step 1 より

$$
1 \leq N - C \leq N - 1
$$

です。

ということは、$1 \leq A \leq N - 1$、$1 \leq B \leq N - 1$ を前提として、$A \times B \leq N - 1$ を満たしてさえいれば、$A$、 $B$ はどんな値をとってもいいことになります。$A \times B$ がどんな値になっても、$C$ で辻褄を合わせて条件式 $A \times B + C = N$ を成り立たせることができます。

step 4: A * B ≦ N - 1 を満たす (A, B) の組を求める

わかりやすさのため、具体例として $N = 6$ の場合を考えてみます。
条件 $A \times B \leq N - 1 = 5$ を満たす (A, B) の組を以下に列挙します。

A	B
1	1
1	2
1	3
1	4
1	5
2	1
2	2
3	1
4	1
5	1

$A$ の値に対し条件を満たす $B$ は、$\lfloor \frac{5}{A} \rfloor$ 個あることがわかります。
一般化すると、$\lfloor \frac{N-1}{A} \rfloor$ 個です。

したがって、$A$ を $1$ から $N - 1$ の範囲で変化させることで、各 $A$ における条件を満たす正整数の組 $(A, B, C)$ の数を各回即座に得ることができます。
以下のような関数 getABCCombinationsCount_improve() で $O(N)$ で解答を得ることが可能です。

int getABCCombinationsCount_improve(int N) {
    int ABCCombinationsCount = 0;
    for (int a = 1; a < N; a++)
    {
        ABCCombinationsCount += (N - 1) / a;
    }
    return ABCCombinationsCount;
}

まとめ

今回の解法ポイントは

• 各変数がとりえる値の範囲の特定
• 式の変形

でした。

ご覧いただきありがとうございました。