これ、一見すると
の計算量が必要に思えてしまうね!
問題概要
正の整数 が与えられる。
かつ
であるような正の整数の組
の個数を求めよ。
制約
の範囲を絞る
約数列挙アルゴリズムなどでもお馴染みの、大小関係から整数の範囲を絞って探索する系!!
まず、 かつ
から、次のことが言える。
より、
直観的には、 の 3 人で
を 3 分割するとき、
の分が一番少ないから、
の分は
以下になるよね......という感じ!
よって、for
文を回して探索するときに、 の範囲を調べれば良いことがわかった。実装するときには、次のように書くとよい!!
for (long long A = 1; A * A * A <= N; ++A) { }
この書き方のメリットは、A <= pow(N, 1.0/3)
などと書くのに比べて、数値誤差の心配もない。
の範囲を絞る
さて、次は が固定して考えよう。このとき、
いう式において、
はもはや定数なので、次のように式変形しておく。
さらに より、次のことが言える。
より、
よって、for
文を回して探索するときに、 の範囲を調べれば良いことがわかった。実装するときには、次のように書くとよい!!
for (long long A = 1; A * A * A <= N; ++A) { for (long long B = A; A * B * B <= N; ++B) { } }
の個数
最後に、 を決めた上で
の個数は次のように求められる。
である
より、
である
これらのことから、 は
以上
以下の整数なので
個
ある。
コード
以上の解法は次のように実装できる。計算量については後で考える。
なお、コンテスト中に、この解法の計算量が大丈夫か不安になった人も多いと思う。心配ならば、入力例 3 () が制約範囲内での最大ケースになっているので、それを試すのがよさそうである。このケースで十分高速なら大丈夫!
#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 * A <= N; ++A) { for (long long B = A; A * B * B <= N; ++B) { res += N / (A * B) - B + 1; } } cout << res << endl; }
計算量
の動く範囲を整理すると、次のようになる。
2 個目の について、
より、
となるので、 の探索には
という計算量が必要な気がしてしまう。もし本当にそうなら、
では間に合わない。
しかし実は、上記条件を満たす の組の個数は
と評価できることが示せる。editorial に詳細解説がある。
直観的には、 という式において、3 変数のうち 2 変数を動かして考えているのだから、
になるんだな......と理解することにする。
となる
の探索も同様に
の計算量となるだろう。