結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

struct Erat{
    vector<int> spf;
    vector<bool> prime_table;
    vector<int> mobius;

    Erat(int m){
        assert(m <= 10000000);
        spf.resize(m+1, -1);
        prime_table.resize(m+1, 1);
        mobius.resize(m+1, 1);
        prime_table[0] = 0;
        prime_table[1] = 0;
        spf[1] = 1;
        for (int i=2; i<=m; i++){
            if (prime_table[i]){
                spf[i] = i;
                mobius[i] = -1;
                for (int j=i*2; j<=m; j+=i){
                    prime_table[j] = 0;
                    if (spf[j] == -1) spf[j] = i;
                    if ((j/i) % i == 0) mobius[j] = 0;
                    else mobius[j] = -mobius[j];
                }
            }
        }
    }

    map<int, int> prime_factor(int n) const{
        map<int, int> res;
        while(n != 1){
            res[spf[n]]++;
            n /= spf[n];
        }
        return res;
    }

    vector<int> all_factor(int n) const{
        vector<int> res={1};
        map<int, int> prime = prime_factor(n);
        for (auto [p, e] : prime){
            int x=1, m=res.size();
            for (int j=0; j<e; j++){
                x *= p;
                for (int k=0; k<m; k++) res.push_back(res[k] * x);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }

    inline bool is_prime(int n) const{return prime_table[n];}

    template<typename T>
    vector<T> fast_zeta(const vector<T> &vec) const{
        int n = vec.size();
        vector<T> res=vec;
        for (int i=2; i<n; i++){
            if (!is_prime(i)) continue;
            for (int j=(n-1)/i; j>=1; j--) res[j] += res[j*i];
        }
        return res;
    }

    template<typename T>
    vector<T> fast_mobius(const vector<T> &vec) const{
        int n = vec.size();
        vector<T> res=vec;
        for (int i=2; i<n; i++){
            if (!is_prime(i)) continue;
            for (int j=1; i*j<n; j++) res[j] -= res[j*i];
        }
        return res;
    }

    template<typename T>
    vector<T> gcd_convolution(const vector<T> & _f, const vector<T> & _g){
        vector<T> f=_f, g=_g, h;
        int n = max(f.size(), g.size());
        f.resize(n);
        g.resize(n);
        h.resize(n);
        f = fast_zeta(f);
        g = fast_zeta(g);
        for (int i=1; i<n; i++) h[i] = f[i] * g[i];
        return fast_mobius(h);
    }
};

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    ll ans=0, N;
    cin >> N;
    Erat erat(100000);
    for (int p=1; p<=100000; p++){
        if (erat.is_prime(p)){
            ll pw=(ll)p*p;
            while(pw<=N){
                ans += pw;
                pw *= p;
            }
        }
    }
    cout << ans << endl;

    return 0;
}
0