でもできる!
問題概要
正の整数 が与えられる。
を満たすような正の整数 の組の個数を求めよ。
制約
考えたこと
こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる!!
というわけで、まずは単純に全探索することを考えてみよう。 の値を全部調べてみる。
より大きい値まで調べる必要はないので、
をすべて調べて、 となるものを数え上げれば OK。しかしこのままでは
の計算量となってしまう。
こういうときは、「どの変数を固定して考えたらいい感じに数えられるか」を考えることが大切だと思う。
C を固定すると...
このとき、 となって、
の約数を数え上げる問題になる!!!
しかし約数列挙には の計算量を要するので、全体で
になってしまう。ちょっと苦しい (一応通せるみたい)。
なお、明らかに 300 点問題の解法ではないが、エラトステネスのふるいを活用して、 全体の素因数分解を
でできる方法もある。
A を固定すると...(対称性から B も一緒)
この場合は、関係式は
- (
の倍数) +
=
という風になる。この関係式をよくみると
の倍数を 1 個決めると、
- (
の倍数) と決まる
- ただし、
の倍数は
未満でなければならない
ということがわかる。つまり、問題を言い換えると次のようになる。
以下の整数のうち、
の倍数は何個あるか?
これの答えは N-1 / A
という式で で求められる。全体の計算量も
になって間に合う。
#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))
よく考えると、 は対象なので対等に扱うことができるので、
の場合
の場合
のみを考えればよいということになる。このとき答えは
- (1 の場合の数) + (2 の場合の数) × 2
で求められる。
A = B の場合
このとき、 となるので、これはつまり
以下の平方数が何個あるかを問う問題となる。単純に 1 から順に平方数を列挙しても
で求められる。
A < B の場合
このとき、 となることから、
となる。よって、先ほどと同様に次のようにして求められる。
について
以下の
の倍数の個数を求めて合算していく
- ただし
なので、
(最初の
個) は除外する
- ただし
各 に対して
で計算できるので、全体の計算量も
で求められる。
#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; }