結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vec<T>, greater<T>>;
#define rep(i, r) for(ll i = 0; i < (r); i++)
#define reps(i, l, r) for(ll i = (l); i < (r); i++)
#define rrep(i, l, r) for(ll i = (r) - 1; i >= (l); i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
template<typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }
ll modmul(ll a, ll b, ll mod) {
	ll ret = a * b - mod * ll(1.L / mod * a * b);
	return ret + mod * (ret < 0) - mod * (ret >= mod);
}
ll modpow(ll a, ll b, ll mod) {
	ll ans = 1;
	for (; b; a = modmul(a, a, mod), b /= 2)
		if (b & 1) ans = modmul(ans, a, mod);
	return ans;
}

using ull = unsigned long long;

int solve() {
    ll n;
    cin >> n;
    vec<bool> is_prime(100'001, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for(ll p=2; p*p<=n; p++) {
        if(!is_prime[p]) continue;
        for(ll x=p*2; x<100'001; x+=p) {
            is_prime[x] = false;
        }
    }
    ll ans = 0;
    reps(p, 2, 100'001) {
        if(!is_prime[p]) continue;
        ll tmp = p * p;
        while(true) {
            if(tmp <= n) {
                ans += tmp;
                // cout << tmp << endl;
                tmp *= p;
            }
            else break;
        }
    }
    cout << ans << endl;
    return 0;
}

int main() {
	ll T = 1;
	cout << fixed << setprecision(16);
	// cin >> T;
	while (T--) solve();
}
0