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

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

AtCoder ABC 250 D - 250-like Number (茶色, 400 点)

緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね!

前提知識

問題概要

素数  p \lt q を用いて  pq^{3} と表される数を「250 に似た数」であると言います。

整数  N が与えられますので、 1 以上  N 以下の「250 に似た数」の個数を求めてください。

制約

  •  1 \le N \le 10^{18}

考えること

まずは全探索に基づく解法を考えてみましょう!! 一般に数学的な見た目の問題では、過度に怖がらずに、落ち着いて全探索解法を考えることで活路を見出せることが多いです!!

 p, q を全探索すればよいのですから、次のように実装できます。

long long res = 0;  // 求める個数
for (long long p = 1; p <= N; ++p) {
    if (p が素数でない) continue;
    for (long long q = p + 1; p * q * q * q <= N; ++q) {
        if (q が素数) ++res;
    }
}

まずはこういう発想ができることがとても大切です。このアルゴリズムを少しずつ改善していきましょう。

 

改善 1:変数を固定して考える

今回の問題では 2 つの変数  p, q が登場します。これらを同時に動かして考えているから、アルゴリズムの効率が悪いのです。そこで重要な考え方は


変数を 1 つ固定して考える


というものです (類題たち)。ものすごく使える考え方ですので、ぜひともマスターしたいところです!!

さて、今回変数を固定するにあたって、戦略は 2 つ考えられます。

  1. 変数  p を固定する
  2. 変数  q を固定する

このうちのどちらをとっても、AC に辿り着けます。ここでは変数  q を固定する方を選択します。なお、変数  p を固定する方法については、公式解説に載っています。

atcoder.jp

変数  q の値を決め打つ前に、変数  q が動く範囲を考えてみましょう。

 pq^{3} \le N

なのですから、最悪でも  q^{3} \le N です。よって、 q \le N^{\frac{1}{3}} です。

 N \le 10^{18} より、 q \le 10^{6} の範囲を調べれば十分だと言えます。

 q を固定して考える解法は、全体としては次のように実装します。

long long res = 0;  // 求める個数
for (long long q = 2; q * q * q <= N; ++q) {
    if (q が素数でない) continue;
    
    // p は p < q と p * q^3 <= N を満たす素数である
    // そのような p の個数は、min(q - 1, N / q / q / q) 以下の素数の個数である
    long long pmax = min(q - 1, N / q / q / q);
    res += (pmax 以下の素数の個数);
}

 

改善 2:エラトステネスのふるいで素数列挙

エラトステネスのふるいを用いると、素数を列挙できます。今回は  p \lt q \le 10^{6} であると分かっているので、 10^{6} 以下の素数を調べれば十分です。

エラトステネスのふるいによって、 10^{6} 以下の素数を列挙して、以下の配列を求めましょう。


prs[i]i 番目の素数


この配列を用いると、今回の問題を解くコードは次のように改良できます。

long long res = 0;  // 求める個数
for (long long q : prs) {
    if (q * q * q > N) break;

    // p は p < q と p * q^3 <= N を満たす素数である
    // そのような p の個数は、min(q - 1, N / q / q / q) 以下の素数の個数である
    long long pmax = min(q - 1, N / q / q / q);
    res += (pmax 以下の素数の個数);
}

 

改善 3:二分探索

最後に、整数 pmax に対して「pmax 以下の素数の個数」を求める方法を考えましょう。

実は素数を列挙した配列 prs さえあれば、二分探索によって容易に求められます。

  1.  x 番目 (0-indexed) の素数が pmax より大きい最小の  x を二分探索で求める
  2. このとき、 x は「pmax 以下の素数の個数」を表す

このうちの 1 の部分は、二分探索法で求められます。 計算量は 「 N^{\frac{1}{3}} 以下の素数の個数を  P としたとき、 O(\log P) です。

 10^{6} 以下のすべての素数  q に対して二分探索を実施しても、十分間に合います。

 

コード

以上の工夫をすべて取り入れたコードは次のように書けます。

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

vector<int> Era(int n) {
    vector<int> res;
    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]) {
            res.push_back(i);
            for (int j = i*2; j < n; j += i) {
                isprime[j] = false;
            }
        }
    }
    return res;
}

int main() {
    long long N;
    cin >> N;

    // エラトステネスのふるい
    vector<int> prs = Era(1000000);

    long long res = 0;
    for (long long q : prs) {
        if (q * q * q > N) break;

        long long pmax = min(q - 1, N / q / q / q);

        // pmax 以下の素数の個数を二分探索で求める
        long long low = -1, high = prs.size();
        while (high - low > 1) {
            long long x = (low + high) / 2;
            if (prs[x] > pmax) high = x;
            else low = x;
        }
        res += high;
    }
    cout << res << endl;
}