#1027979 (C++23) No.713 素数の和

提出ソース
結果

問題	No.713 素数の和
コンテスト
ユーザー	tonegawa
提出日時	2024-11-22 16:47:09
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	12,342 bytes
コンパイル時間	2,598 ms
コンパイル使用メモリ	189,576 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-22 16:47:12
合計ジャッジ時間	3,488 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 6
権限があれば一括ダウンロードができます
ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}





#include <cstdint>

uint64_t random64() {
    static std::random_device seed_gen;
    static std::mt19937_64 engine(seed_gen());
    return engine();
}

struct hash_fast {
    static uint64_t r64;
    static uint32_t r32;

    static uint64_t hash_u64(uint64_t x) {
        x += r64;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return (x ^ (x >> 31));
    }

    static uint32_t hash_u32(uint32_t x) {
        x += r32;
        x = (x ^ (x >> 16)) * 0x7feb352d;
	    x = (x ^ (x >> 15)) * 0x846ca68b;
	    return x ^ (x >> 16);
    }

    // ペアのハッシュ {x, y}と{y, x}は異なるとする
    static uint64_t hash_u64_u64(std::pair<uint64_t, uint64_t> p) {
        return hash_u64(hash_u64(p.first) + p.second);
    }

    // ペアのハッシュ {x, y}と{y, x}は異なるとする
    static uint64_t hash_u32_u32(std::pair<uint32_t, uint32_t> p) {
        return hash_u64(((uint64_t)p.first << 32) + p.second);
    }

    template<typename T>
    static uint64_t hash(T x) { assert(false); }
    static uint64_t hash(uint64_t x) { return hash_u64(x); }
    static uint64_t hash(long long x) { return hash_u64(x); }
    static uint64_t hash(uint32_t x) { return hash_u32(x); }
    static uint64_t hash(int x) { return hash_u32(x); }
    static uint64_t hash(std::pair<uint64_t, uint64_t> x) { return hash_u64_u64(x); }
    static uint64_t hash(std::pair<uint32_t, uint32_t> x) { return hash_u32_u32(x); }
};
uint64_t hash_fast::r64 = random64();
uint32_t hash_fast::r32 = random64();





constexpr unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

constexpr int bit_ceil_log(unsigned int n) {
    int x = 0;
    while ((1 << x) < (unsigned int)(n)) x++;
    return x;
}


// 高速化のために以下のような実装
// ・INF<S>とINF<T>を無効な値にする(入れると壊れる)
// ・サイズの縮小を行わなないため要素列挙を行えない 
template<typename S, typename T>
struct hash_map {
  private:
    static constexpr S _NULL = std::numeric_limits<S>::max();
    static constexpr T _ERASED = std::numeric_limits<T>::max();
    int _size_mod; // table.size() - 1
    int _cnt_data; // データサイズ
    std::vector<std::pair<S, T>> table;
    static constexpr double max_ratio = 0.7;
    static constexpr int init_size = 8;

    void expand() {
        _size_mod = _size_mod * 2 + 1;
        std::vector<std::pair<S, T>> tmp(_size_mod + 1, {_NULL, _ERASED});
        std::swap(tmp, table);
        _cnt_data = 0;
        for (auto [key, val] : tmp) {
            if (key != _NULL && val != _ERASED) {
                emplace(key, val);
            }
        }
    }
  
  public:
    hash_map() : _size_mod(init_size - 1), _cnt_data(0), table(_size_mod + 1, {_NULL, _ERASED}) {}
    hash_map(int size) : _size_mod(bit_ceil(size) - 1), _cnt_data(0), table(_size_mod + 1, {_NULL, _ERASED}) {}


    // {追加することができたか、追加後のtable[x]の参照}
    std::pair<bool, T&> emplace(S x, T y) {
        if (max_ratio * _size_mod < _cnt_data) expand();
        int i = hash_fast::hash(x) & _size_mod;
        while (table[i].first != _NULL) {
            if (table[i].first == x) {
                if (table[i].second == _ERASED) {
                    table[i].second = y;
                    return {true, table[i].second};
                } else {
                    return {false, table[i].second};
                }
            }
            i = (i + 1) & _size_mod;
        }
        table[i] = {x, y};
        _cnt_data++;
        return {true, table[i].second};
    }

    // emplaceを行った後にtable[x]をyにする
    // {table[x]が存在しなかったらtrue、追加後のtable[x]の参照}
    std::pair<bool, T&> emplace_replace(S x, T y) {
        if (max_ratio * _size_mod < _cnt_data) expand();
        int i = hash_fast::hash(x) & _size_mod;
        while (table[i].first != _NULL) {
            if (table[i].first == x) {
                bool f = table[i].second == _ERASED;
                table[i].second = y;
                return {f, table[i].second};
            }
            i = (i + 1) & _size_mod;
        }
        table[i] = {x, y};
        _cnt_data++;
        return {true, table[i].second};
    }

    // 削除することができたか
    bool erase(S x) {
        int i = hash_fast::hash(x) & _size_mod;
        while (table[i].first != _NULL) {
            if (table[i].first == x) {
                bool f = table[i].second != _ERASED;
                table[i].second = _NULL;
                return f;
            }
            i = (i + 1) & _size_mod;
        }
        return false;
    }

    // {存在するか、存在する場合その値の参照}
    std::pair<bool, T&> find(S x) {
        int i = hash_fast::hash(x) & _size_mod;
        while (table[i].first != _NULL) {
            if (table[i].first == x) {
                return {table[i].second != _ERASED, table[i].second};
            }
            i = (i + 1) & _size_mod;
        }
        return {false, table[i].second};
    }
};


template<typename T>
std::vector<T> enumerate_quotients(T x) {
    assert(x >= 0);
    if (x == 0) return {};
    T sq = sqrtl(x);
    std::vector<T> ans(sq);
    std::iota(ans.begin(), ans.end(), 1);
    if (x / sq == sq) sq--;
    for (T i = sq; i >= 1; i--) ans.push_back(x / i);
    return ans;
}

long long counting_primes(long long n) {
    assert(n >= 0);
    if (n == 0) return 0;
    int sq = sqrt(n);
    std::vector<bool> is_prime(sq + 1, true);
    std::vector<long long> Fprime(sq + 1, 0);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p <= sq; p++) {
        Fprime[p] = Fprime[p - 1] + is_prime[p];
        if (!is_prime[p]) continue;
        for (int i = 2 * p; i <= sq; i += p) is_prime[i] = false;
    }
    auto Q = enumerate_quotients<long long>(n);
    int W = Q.size();
    std::vector<long long> f(W);
    for (int i = 0; i < W; i++) f[i] = Q[i] - 1;
    for (int p = 2; p <= sq; p++) {
        if (!is_prime[p]) continue;
        long long p2 = (long long)p * p;
        if (p2 <= sq) {
            for (int i = W - 1, j = W - 1; i >= 0 && Q[i] >= p2; i--) {
                while (j >= 0 && Q[j] > Q[i] / p) j--;
                f[i] -= f[j] - Fprime[p - 1];
            }
        } else {
            for (int i = W - 1; i >= 0 && Q[i] >= p2; i--) {
                long long x = Q[i] / p;
                int j = (x <= sq ? x - 1 : W - n / x);
                f[i] -= f[j] - Fprime[p - 1];
            }
        }
    }
    return f[W - 1];
}


long long prefixsum_primes(long long n) {
    assert(n >= 0);
    if (n == 0) return 0;
    int sq = sqrt(n);
    std::vector<bool> is_prime(sq + 1, true);
    std::vector<long long> Fprime(sq + 1, 0);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p <= sq; p++) {
        Fprime[p] = Fprime[p - 1] + (is_prime[p] ? p : 0);
        if (!is_prime[p]) continue;
        for (int i = 2 * p; i <= sq; i += p) is_prime[i] = false;
    }
    auto Q = enumerate_quotients<long long>(n);
    int W = Q.size();
    std::vector<long long> f(W);
    for (int i = 0; i < W; i++) f[i] = (Q[i] * (Q[i] + 1)) / 2 - 1;
    for (int p = 2; p <= sq; p++) {
        if (!is_prime[p]) continue;
        long long p2 = (long long)p * p;
        if (p2 <= sq) {
            for (int i = W - 1, j = W - 1; i >= 0 && Q[i] >= p2; i--) {
                while (j >= 0 && Q[j] > Q[i] / p) j--;
                f[i] -= p * (f[j] - Fprime[p - 1]);
            }
        } else {
            for (int i = W - 1; i >= 0 && Q[i] >= p2; i--) {
                long long x = Q[i] / p;
                int j = (x <= sq ? x - 1 : W - n / x);
                f[i] -= p * (f[j] - Fprime[p - 1]);
            }
        }
    }
    return f[W - 1];
}



int main() {
    long long N;
    std::cin >> N;
    std::cout << prefixsum_primes(N) << '\n';
}
yukicoder

結果

ソースコード
