提出 #57461044

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;
constexpr ll INF = 1e12 + 7;
constexpr ll mod = 1e9 + 7;
constexpr ld eps = 1e-9;
const ld PI = acos(-1);

vector<int> Mobius(int n) {
    vector<int> mobius(n + 1, 0);
    vector<int> sv(n + 1, 0);
    sv[1] = 1;
    for (int i = 2; i * i <= n; ++i) {
        if (sv[i])continue;
        sv[i] = i;
        for (ll j = i * i; j <= n; j += i) {
            if (!sv[j])sv[j] = i;
        }
    }
    mobius[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!sv[i])sv[i] = i;
        if (sv[i] == sv[i / sv[i]])mobius[i] = 0;
        else mobius[i] = -1 * mobius[i / sv[i]];
    }
    return mobius;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n;
    cin >> n;
    ll res = 0;
    auto cnt = [&](ll x) {
        ll l = 1, r = n + 1;
        while (r - l > 1) {
            ll m = (r + l) / 2;
            ll val = 1;
            for (ll i = 0; i < x && val <= n; ++i) {
                if (val > n / m)val = n + 1;
                else val *= m;
            }
            (val <= n ? l : r) = m;
        }
        return l;
    };
    constexpr ll K = 62;
    auto m = Mobius(K);
    for (ll b = 2; b <= K; ++b) {
        res += -m[b] * (cnt(b)-1);
    }
    cout << ++res;
}

提出情報

ジャッジ結果