結果

問題 No.106 素数が嫌い！2
コンテスト
ユーザー Tatsu_mr
提出日時 2024-10-24 14:01:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 91 ms / 5,000 ms
コード長 2,582 bytes
コンパイル時間 3,912 ms
コンパイル使用メモリ 257,524 KB
実行使用メモリ 19,848 KB
最終ジャッジ日時 2024-10-24 14:01:34
合計ジャッジ時間 5,507 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define For(i, a, b) for(long long i = a; i < b; i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(long long i = a; i >= b; i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
using namespace std;

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

struct Sieve {
    private:
    int n;
    vector<int> IdxtoVal, ValtoIdx;
    vector<bool> deleted;
    
    void build() {
        int sz = (n % 30 == 0 ? n / 30 : n / 30 + 1);
        sz *= 8;
        IdxtoVal = {1, 7, 11, 13, 17, 19, 23, 29};
        for (int i = 0; i < 8; i++) {
            ValtoIdx[IdxtoVal[i]] = i;
        }
        deleted.assign(sz, false);
        for (int i = 1; i < sz; i++) {
            if (deleted[i]) {
                continue;
            }
            int p = getval(i);
            for (int j = i; j < sz; j++) {
                int q = getval(j);
                if (q > n / p) {
                    break;
                }
                deleted[getidx(p * q)] = true;
            }
        }
    }
    
    int getval(int i) {
        return i / 8 * 30 + IdxtoVal[i % 8];
    }
    
    int getidx(int x) {
        return x / 30 * 8 + ValtoIdx[x % 30];
    }
    
    public:
    Sieve(int n_) : n(n_), IdxtoVal(8), ValtoIdx(30) {
        build();
    }
    
    bool isprime(int x) {
        if (x == 1) {
            return false;
        } else if (x == 2 || x == 3 || x == 5) {
            return true;
        } else if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0) {
            return false;
        } else {
            return !deleted[getidx(x)];
        }
    }
    
    vector<int> primes() {
        vector<int> res;
        for (int i = 2; i <= n; i++) {
            if (isprime(i)) {
                res.emplace_back(i);
            }
        }
        return res;
    }
};

int main() {
    lint n, k;
    cin >> n >> k;
    auto ps = Sieve(n).primes();
    vector<int> ans(n + 1), used(n + 1);
    vector<bool> visit(n + 1, false);
    auto dfs = [&](auto dfs, lint now, int cnt) -> void {
        visit[now] = true;
        if (cnt >= k) {
            ans[now] = 1;
        }
        for (lint p : ps) {
            lint nnow = now * p;
            if (nnow > n) {
                break;
            }
            if (visit[nnow]) {
                continue;
            }
            used[p]++;
            dfs(dfs, nnow, cnt + (used[p] == 1));
            used[p]--;
        }
    };
    dfs(dfs, 1LL, 0);
    cout << accumulate(ALL(ans), 0) << endl;
}
0