結果

問題 No.144 エラトステネスのざる
コンテスト
ユーザー joji
提出日時 2026-01-23 16:06:06
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 375 ms / 2,000 ms
コード長 4,737 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,938 ms
コンパイル使用メモリ 342,624 KB
実行使用メモリ 15,948 KB
最終ジャッジ日時 2026-01-23 16:06:14
合計ジャッジ時間 7,701 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 2 "nt/sieve.hpp"
#include <cstdint>
#include <vector>

namespace NT {
struct Sieve {
        int N;
        std::vector<int> primes;
        std::vector<int> spf;
        std::vector<int> phi;
        std::vector<int> mu;
        Sieve(int max_n) : N(max_n), spf(max_n + 1, 0), phi(max_n + 1), mu(max_n + 1) {
                phi[1] = 1;
                mu[1] = 1;
                for (int i = 2; i <= N; i++) {
                        if (spf[i] == 0) {
                                spf[i] = i;
                                primes.push_back(i);
                                phi[i] = i - 1;
                                mu[i] = -1;
                        }
                        for (int p : primes) {
                                if (p > spf[i] || (int64_t)i * p > N) break;
                                spf[i * p] = p;
                                if (spf[i] == p) {
                                        phi[i * p] = phi[i] * p;
                                        mu[i * p] = 0;
                                        break;
                                } else {
                                        phi[i * p] = phi[i] * (p - 1);
                                        mu[i * p] = -mu[i];
                                }
                        }
                }
        }
        bool is_prime(int x) const {
                if (x <= 1 || x > N) return false;
                return spf[x] == x;
        }
        std::vector<std::pair<int, int>> get_prime_factors(int x) const {
                std::vector<std::pair<int, int>> factors;
                while (x > 1) {
                        int p = spf[x];
                        int exponent = 0;
                        while (x % p == 0) {
                                x /= p;
                                exponent++;
                        }
                        factors.push_back({p, exponent});
                }
                return factors;
        }
        std::vector<int> get_distinct_primes(int x) const {
                std::vector<int> distinct;
                while (x > 1) {
                        int p = spf[x];
                        distinct.push_back(p);
                        while (x % p == 0) x /= p;
                }
                return distinct;
        }
        int64_t count_divisors(int x) const {
                if (x == 1) return 1;
                int64_t res = 1;
                while (x > 1) {
                        int p = spf[x];
                        int e = 0;
                        while (x % p == 0) {
                                x /= p;
                                e++;
                        }
                        res *= (e + 1);
                }
                return res;
        }
        int64_t sum_divisors(int x) const {
                if (x == 1) return 1;
                int64_t res = 1;
                while (x > 1) {
                        int p = spf[x];
                        int64_t sum_p = 1, p_pow = 1;
                        while (x % p == 0) {
                                x /= p;
                                p_pow *= p;
                                sum_p += p_pow;
                        }
                        res *= sum_p;
                }
                return res;
        }
        std::vector<int64_t> get_all_divisors(int x) const {
                auto factors = get_prime_factors(x);
                std::vector<int64_t> divs = {1};
                for (auto &pf : factors) {
                        int p = pf.first;
                        int count = pf.second;
                        int sz = divs.size();
                        int64_t cur_p = 1;
                        for (int i = 0; i < count; ++i) {
                                cur_p *= p;
                                for (int j = 0; j < sz; ++j) {
                                        divs.push_back(divs[j] * cur_p);
                                }
                        }
                }
                return divs;
        }
};
} // namespace NT
#line 2 "144.test.cpp"
#include <bits/stdc++.h>

using namespace std;

void solve() {
        int N;
        long double p, ans = 0.0;
        cin >> N >> p;
        NT::Sieve sieve(1000000);
        for (int i = 2; i <= N; i++) {
                if (sieve.is_prime(i)) {
                        ans += 1.0;
                } else {
                        ans += pow(1 - p, sieve.count_divisors(i) - 2);
                }
        }
        cout << fixed << setprecision(12) << ans << '\n';
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        int t = 1;
        // cin >> t;
        while (t--) solve();

        return 0;
}
0