ABC 300

Wed, Jul 16, 2025

https://atcoder.jp/contests/abc300

A. N-choice question

https://atcoder.jp/contests/abc300/tasks/abc300_a

B. Same Map in the RPG World

https://atcoder.jp/contests/abc300/tasks/abc300_b

C. Cross

https://atcoder.jp/contests/abc300/tasks/abc300_c

D. AABCC

https://atcoder.jp/contests/abc300/tasks/abc300_d

$a < b < c$ と $300 \leq N \leq 10^{12}$ より素数は $10^6$ までのものを考えれば十分である。

$a^5 < a^2 b c^2 \leq N \Rightarrow a < N^{1/5} = ( 10^{12} )^{1/5} \approx 251.18$

$b^3 < b c^2 < N/a^2 \Rightarrow b < (N/a^2)^{1/3}$

\begin{align*} \int_{1}^{(10^{ 12 })^{1/5}} \left( \frac{10^12}{x^2} \right)^{1/3} dx \approx 1.592 \times 10^5 \end{align*}

$a, b$ が決まったとき、$c$ の候補は $(b, N/(a^2 b)]$ の範囲にある素数である。これは二分探索を用いることで個数を求めることができる。

以上より最悪でも $251.185 \times 1.592 \times 10^5 \times \log_2 10^6 = 7.97 \times 10^8$ の計算量に収まる。

https://www.wolframalpha.com/input?i=integral+from+1+to+251+of+%2810%5E12%2Fx%5E2%29%5E%281%2F3%29+dx

実際は $c$ を二分探索するまでもなく $b < c$ なる $c$ が選べないケースが多いので、もっと少ない計算量で済む。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m = (int)1e6 + 5;
    vint isp(m, 1);
    isp[0] = isp[1] = 0;
    rep2(i, 2, m) {
        for (ll j = i + i; j < m; j += i) {
            isp[j] = 0;
        }
    }

    vll primes;
    rep(i, m) if (isp[i]) primes.push_back(i);

    using ull = unsigned long long int;

    auto kth_root = [](ull x, int k) -> ull {
        assert(k != 0);
        if (x == 1 || k == 1) return x;
        ull l = 0, r = x;
        while (r - l > 1) {
            ull m = (r - l) / 2 + l;
            ull t = x;
            rep(i, k) t /= m;
            if (1 > t) {
                r = m;
            } else {
                l = m;
            }
        }
        return l;
    };

    // 平方根
    auto isqrt = [&](ull x) -> ull {
        return kth_root(x, 2);
    };

    ll N;
    cin >> N;

    ll ans = 0;

    rep(i, m) {
        ll a = primes[i];
        if (a * a * a * a * a > N) break;
        rep2(j, i + 1, m) {
            ll b = primes[j];
            if (b * b * b > N / a / a) break;
            ll csq_upper = N / (a * a * b);
            ll c = isqrt(csq_upper);
            if (b < c) {
                auto lit = lower_bound(all(primes), b);
                auto rit = prev(upper_bound(all(primes), c));
                ans += rit - lit;
            }
        }
    }

    cout << ans << endl;
}