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

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

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

 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 は対象なので対等に扱うことができるので、

  1.  A = B の場合
  2.  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} について
  •  N-1 以下の  A の倍数の個数を求めて合算していく
    • ただし  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;
}