ほどよい全探索問題！　約数列挙のアルゴリズムなどをちゃんと理解していれば解ける！

問題へのリンク

問題概要

$N$ 以下の正整数のうち、 $a \lt b \lt c$ なる素数 $a, b, c$ を用いて $a^{2} \times b \times c^{2}$ と表せるものはいくつあるか？

制約

$300 \le N \le 10^{12}$

前提知識

この問題を見てまったく見当もつかないという場合には、「約数列挙」アルゴリズムをまず勉強するとよさそう！！

次の記事の 3 章までを勉強すると、今回のこの問題にも手がつけられるようになると思う！

qiita.com

簡単に復習してみる。

正整数 $N$ の約数をすべて求めるアルゴリズムの肝は「 $\sqrt{N}$ まで試せば十分」という点にある。その理由が大切だ。

$a$ を $N$ の約数としたとき、整数 $b$ を用いて

$a \times b = N$

と表せる。ここで、 $a \le b$ であると仮定しよう (そうでない場合も同様に求められる)。このとき、

$N = a \times b \ge a \times a \ge a^{2}$

となるので、 $a \le \sqrt{N}$ となる。よって、 $a$ を $1$ から $\sqrt{N}$ まで順に試せば良いことがわかった。計算量は $O(\sqrt{N})$ となる。

今回の問題でも

今回の問題も、基本的には全探索アルゴリズムで解ける。このとき、 $a$ をどこまで試せばよいかが肝となる。

$a$ の範囲を絞る

$a \lt b \lt c$ より、

$\displaystyle N \ge a^{2} \times b \times c^{2} \gt a^{2} \times a \times a^{2} = a^{5}$

となります。このことから、

$\displaystyle a \lt N^{\frac{1}{5}}$

とわかります。ざっくり「一番小さい数は十分小さくなるはず」と信じて、不等式評価する感じですね。 $N \le 10^{12}$ なので、 $a \le 300$ 程度まで試せば十分だとわかります。

$b$ の範囲を絞る

次に $a$ を固定したときの $b$ の範囲を考えます。最悪の場合として $a = 1$ のときを考えることにしましょう (1 は素数ではないですが......)。このとき、

$N \ge b \times c^{2} \gt b \times b^{2} = b^{3}$

となります。このことから、

$\displaystyle b \lt N^{\frac{1}{3}}$

とわかります。 $N \le 10^{12}$ なので、 $b \le 10000$ まで試せば十分だとわかります。

$c$ の個数を求める

最後に、 $a, b$ を固定したとき、

$b \lt c$
$a^{2} \times b \times c^{2} \le N$

を満たす素数 $c$ の個数を考えます。つまり、

$b \lt c \le \displaystyle \sqrt{\frac{N}{a^{2}b}}$

を満たすような素数 $c$ の個数を求めれば良いです。これは

あらかじめ、エラトステネスの篩を用いて、各整数が素数かどうかを調べておいて
その累積和をとっておくことで
$O(1)$ の計算量で求められます。

このことがピンと来ない場合には、次の記事の「問題 2： AtCoder ABC 084 D - 2017-like Number」のところまで読めば、納得できるはずです！

qiita.com

なお、 $N \ge a^{2} \times b \times c^{2} \ge c^{2}$ なので、

$c \le \sqrt{N}$

となります。 $N \le 10^{12}$ より、 $10^{6}$ 以下の整数について、エラトステネスの篩を適用すれば十分です。

おまけ：正確な計算量

正確な計算量を見積もってみます。

最初にエラトステネスの篩を適用する部分： $O(\sqrt{N} \log \log N)$
その累積和を求める部分： $O(\sqrt{N})$
$a, b$ を全探索する部分： $O(N^{\frac{1}{5}} \times N^{\frac{1}{3}}) = O(N^{\frac{8}{15}})$

となります。つまり全体の計算量は $O(N^{\frac{8}{15}})$ となります。

コード

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

// エラトステネスの篩
vector<bool> Era(int n) {
    vector<bool> isprime(n, true);
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n; ++i) isprime[i] = true;
    for (int i = 2; i < n; ++i) {
        if (isprime[i]) {
            for (int j = i*2; j < n; j += i) isprime[j] = false;
        }
    }
    return isprime;
}

int main() {
    long long N;
    cin >> N;
    
    // 10^6 以下の整数が素数かどうかを求めておく
    const int MAX = 1100000;
    vector<bool> isprime = Era(MAX);
    
    // l 以上 r 未満の素数の個数を数えられるようにするための累積和
    vector<long long> S(MAX + 1, 0);
    for (int i = 0; i < MAX; ++i) S[i+1] = S[i] + isprime[i];
    
    // 数える
    long long res = 0;
    for (long long a = 1; a * a * a * a * a <= N; ++a){
        if (!isprime[a]) continue;
        for (long long b = a + 1; b * b * b <= N; ++b) {
            if (!isprime[b]) continue;
            
            // b+1 以上 N/a^2b 以下の素数の個数を足す
            long long cmax = sqrt(N/a/a/b);
            if (b + 1 <= cmax + 1) res += S[cmax + 1] - S[b + 1];
        }
    }
    cout << res << endl;
}

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

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

AtCoder ABC 300 D - AABCC (緑色, 400 点)