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

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

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

貴重な区間篩の問題

問題概要

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

  •  L \le x \le R
  •  x の相異なる素因数の個数が素数

制約

  •  1 \le L \le R \le 10^{9}
  •  R - L \le 10^{6}

考えたこと

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

 p = 2, 3, \dots, \sqrt{R} に対して、

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

というふうにする。それを元にして、各整数  v を高速素因数分解していけば 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;
}