$O(\sqrt{N})$ でもできる！

問題概要

正の整数 $N$ が与えられる。

$A \times B + C = N$

を満たすような正の整数 $(A, B, C)$ の組の個数を求めよ。

制約

$2 \le N \le 10^{6}$

考えたこと

こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる！！

というわけで、まずは単純に全探索することを考えてみよう。 $A, B, C$ の値を全部調べてみる。 $N$ より大きい値まで調べる必要はないので、

$A = 1, 2, \dots, N$
$B = 1, 2, \dots, N$
$C = 1, 2, \dots, N$

をすべて調べて、 $A \times B + C = N$ となるものを数え上げれば OK。しかしこのままでは $O(N^{3})$ の計算量となってしまう。

こういうときは、「どの変数を固定して考えたらいい感じに数えられるか」を考えることが大切だと思う。

C を固定すると...

このとき、 $A \times B = N - c$ となって、 $N - c$ の約数を数え上げる問題になる！！！

しかし約数列挙には $O(\sqrt{N})$ の計算量を要するので、全体で $O(N\sqrt{N})$ になってしまう。ちょっと苦しい (一応通せるみたい)。

なお、明らかに 300 点問題の解法ではないが、エラトステネスのふるいを活用して、 $1, 2, \dots, N$ 全体の素因数分解を $O(N \log N)$ でできる方法もある。

A を固定すると...(対称性から B も一緒)

この場合は、関係式は

( $A$ の倍数) + $C$ = $N$

という風になる。この関係式をよくみると

$A$ の倍数を 1 個決めると、 $C = N$ - ( $A$ の倍数) と決まる
ただし、 $A$ の倍数は $N$ 未満でなければならない

ということがわかる。つまり、問題を言い換えると次のようになる。

$N-1$ 以下の整数のうち、 $A$ の倍数は何個あるか？

これの答えは N-1 / A という式で $O(1)$ で求められる。全体の計算量も $O(N)$ になって間に合う。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long res = 0;
    for (long long a = 1; a < N; ++a) res += (N - 1)/ a;
    cout << res << endl;
}

別解：さらに高速化 (O(√N))

よく考えると、 $A, B$ は対象なので対等に扱うことができるので、

$A = B$ の場合
$A \lt B$ の場合

のみを考えればよいということになる。このとき答えは

(1 の場合の数) + (2 の場合の数) × 2

で求められる。

A = B の場合

このとき、 $A^{2} = N - C$ となるので、これはつまり $N-1$ 以下の平方数が何個あるかを問う問題となる。単純に 1 から順に平方数を列挙しても $O(\sqrt{N})$ で求められる。

A < B の場合

このとき、 $A^{2} \lt AB = N - C \lt N$ となることから、 $A \lt \sqrt{N}$ となる。よって、先ほどと同様に次のようにして求められる。

$A = 1, 2, \dots, \sqrt{N}$ について
以下のの倍数の個数を求めて合算していく
- ただし $A \lt B$ なので、 $A, 2A, \dots, A^{2}$ (最初の $A$ 個) は除外する

各 $A$ に対して $O(1)$ で計算できるので、全体の計算量も $O(\sqrt{N})$ で求められる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long res = 0;
    for (long long A = 1; A * A < N; ++A) ++res;
    for (long long A = 1; A * A < N; ++A) {
        long long num = max((N - 1) / A - A, 0LL);
        res += num * 2;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 179 C - A x B + C (灰色, 300 点)