AtCoder ABC 300 G - P-smooth number (黄色, 600 点)

面白かった

• 問題へのリンク

問題概要

以下の素数のみを素因数に持つ正整数を -smooth number と呼ぶ。

整数 および 、100 以下の素数 が与えられるので、 以下の -smooth number の個数を求めよ。

制約

• 
• 

考えたこと

コンテスト中には、愚直 DFS を頑張って通そうとしてバグを埋め込んでしまった。でも、もろに TLE という雰囲気ではなく、本気で高速化すれば通りそうな雰囲気ではあった (実際に愚直 DFS を通した人もいた)。残り数分の段階で半分全列挙すればよいと思いついたが遅かった。

さて、100 以下の素数を 2 つのグループに分けて、

• 偶数番目の素数のみを素因数にもつ数の集合 evens
• 奇数番目の素数のみを素因数にもつ数の集合 odds

をそれぞれ求めることにした。この場合ありうる最大個数は、evens については 6269654 個、odds については 1913116 個のよう。

そしてこれらの情報をもとに、尺取り法によって、個数を集計する。これで通った。

提出コード

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

// 97 以下の素数の集合
const vector<long long> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

// vals の要素に、素因数 p を加えていく
void add(long long N, long long p, vector<long long> &vals) {
    long long mul = p;
    vector<long long> base({vals});
    while (mul <= N) {
        vector<long long> add;
        for (auto v : base) {
            if (v * mul > N) break;
            add.push_back(v * mul);
        }
        for (auto v : add) vals.push_back(v);
        mul *= p;
    }
    sort(vals.begin(), vals.end());
}

int main() {
    long long N, P;
    cin >> N >> P;
 
    // 偶数番目の素数から作れる数と、奇数番目の素数から作れる数
    vector<long long> evens({1}), odds({1});
    for (int i = 0; i < primes.size(); ++i) {
        if (primes[i] > P) break;
        if (i % 2 == 0) add(N, primes[i], evens);
        else add(N, primes[i], odds);
    }

    // 尺取り法
    long long res = 0;
    long long right = odds.size();
    for (auto v : evens) {
        if (right == 0) break;
        while (right > 0 && v * odds[right-1] > N) --right;
        res += right;
    }
    cout << res << endl;
}