AOJ 2858 Prime-Factor Prime (JAG 模擬地区 2017 C) (350 点)

貴重な区間篩の問題

• 問題へのリンク
• editorial

問題概要

2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。

• 
• の相異なる素因数の個数が素数個

制約

• 
• 

考えたこと

が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使える。

に対して、

• が素数ならば
• 以上 以下の整数 についてのみ
• prime_factors[ ].push_back() と更新していく

というふうにする。それを元にして、各整数 を高速素因数分解していけば OK。計算量は

• エラトステネスの区間篩：
• 各整数の素因数分解：

コード

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

const int MAX = 110000;
long long solve(long long L, long long R) {
    vector<bool> is_prime(MAX, true);
    is_prime[0] = is_prime[1] = false;
    vector<vector<long long>> prime_factors(R-L+1);
    for (long long p = 2; p * p <= R; ++p) {
        if (!is_prime[p]) continue;
        for (long long v = p*2; v < MAX; v += p) {
            is_prime[v] = false;
        }
        for (long long v = (L+p-1)/p*p; v <= R; v += p) {
            prime_factors[v-L].push_back(p);
        }
    }
    long long res = 0;
    for (long long v = L; v <= R; ++v) {
        long long prime_num = 0;
        long long v2 = v;
        const auto& ps = prime_factors[v2-L];
        for (auto p : ps) {
            while (v2 % p == 0) v2 /= p, ++prime_num;
        }
        if (v2 > 1) ++prime_num;
        if (is_prime[prime_num]) ++res;
    }
    return res;
}

int main() {
    long long L, R;
    cin >> L >> R;
    cout << solve(L, R) << endl;
}