結果

問題 No.3296 81-like number
コンテスト
ユーザー Hydrogen
提出日時 2025-10-05 14:08:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,291 bytes
コンパイル時間 3,158 ms
コンパイル使用メモリ 286,884 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 14:08:31
合計ジャッジ時間 3,704 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using uc = unsigned char;
#define Max(X,Y) (((X) > (Y)) ? (X) : (Y))
#define Min(X,Y) (((X) < (Y)) ? (X) : (Y))
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define YES yes return 0;
#define NO no return 0;
#define pc cout << count << endl;
#define PC pc return 0;
#define INF 0x1fffffff
#define Eps LDBL_EPSILON
#ifdef DEBUG
#define dbg(X) cerr << X << endl
#else
#define dbg(...)
#endif

template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) noexcept {
    if(!v.empty()) os << v[0];
    for(size_t i = 1; i < v.size(); i++) os << " " << v[i];
    return os;
}

template <typename T>
void swap(T& a, T& b) {
    auto x = a;
    a = b;
    b = x;
}

template <typename T>
size_t partition(vector<T>& list, size_t start, size_t end) {
    auto pivot = list[end-1];
    auto hi = start;
    for(auto i = start; i < end - 1; i++) {
        if(list[i] <= pivot) {
            swap(list[hi], list[i]);
            hi++;
        }
    }
    swap(list[hi], list[end-1]);
    return hi;
}

template <typename T>
void quicksort(vector<T>& list, size_t l, size_t r) {
    if(l < r) {
        auto pivot = partition(list, l, r);
        quicksort(list, l, pivot);
        quicksort(list, pivot + 1, r);
    }
}

struct string_set {
    map<size_t, vector<string_view>> registry = {};
    bool contains(string_view s) {
        auto h = hash<string_view>()(s);
        return registry.contains(h)
                && find(registry[h].begin(), registry[h].end(), s) != registry[h].end();
    }
    void add(string_view s) {
        auto h = hash<string_view>()(s);
        auto pos = find(registry[h].begin(), registry[h].end(), s);
        if(pos != registry[h].end()) return;
        registry[h].push_back(s);
    }
    void remove(string_view s) {
        auto h = hash<string_view>()(s);
        if(!registry.contains(h)) return;
        auto pos = find(registry[h].begin(), registry[h].end(), s);
        if(pos == registry[h].end()) return;
        registry[h].erase(pos);
    }
};

template <typename T>
struct BIT {
    ll n;
    vector<T> tree;
    BIT(ll size) : n(size + 1), tree(n, 0) {}
    void add(ll i, T x) {
        for (ll idx = i; idx < n; idx += (idx & -idx)) {
            tree[idx] += x;
        }
    }
    T sum(ll i) {
        T s(0);
        for (ll idx = i; idx > 0; idx -= (idx & -idx)) {
            s += tree[idx];
        }
        return s;
    }
};

int main() {
    cin.tie(nullptr);

    ll N;
    cin >> N;
    ll sqN = sqrtl(N);
    ld Nlg = log2l(N);
    vector<char> prime(sqN, 1);
    vector<ll> primes;
    primes.reserve(100000);
    prime[0] = 0;
    primes.push_back(2);
    for(ll i = 4; i <= sqN; i+=2) prime[i-1] = 0;
    for(ll i = 3; i <= sqN; i+=2) {
        if(!prime[i-1]) continue;
        for(ll j = i*i; j <= sqN; j+=i) prime[j-1] = 0;
        primes.push_back(i);
    }
    ll sum = 0;
    for(auto p : primes) {
        ll lim = Nlg/log2l(p);
        ll s = p;
        for(ll i = 0; i < lim; i++) s*=p;
        sum+=(s-1)/(p-1)-p-1;
        // dbg("added " << (s-1)/(p-1)-p-1 << " prime " << p << "lim " << lim);
    }
    cout << sum << endl;
}
0