#740784 (C++14) No.144 エラトステネスのざる

• 問題: No.144 エラトステネスのざる
• ユーザー: dekomori_sanae
• 提出日時: 2022-02-19 13:25:32
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 506 ms / 2,000 ms
• コード長: 2,926 bytes
• コンパイル時間: 899 ms
• コンパイル使用メモリ: 92,140 KB
• 実行使用メモリ: 27,264 KB
• 最終ジャッジ日時: 2024-06-29 10:22:47
• 合計ジャッジ時間: 5,350 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 998244353;
const ll INF = 1e16;
struct Eratosthenes {
    vl isprime;  // isprime[i] : iが素数なら1
    vl minfactor;  // minfactor[i] : iを割り切る最小の素数
    vl mobius;  // mobius[i] : メビウス関数 μ(i)
    Eratosthenes(ll n) : isprime(n+1, 1), 
                         minfactor(n+1, -1), 
                         mobius(n+1, 1) {
        isprime[1] = 0;
        minfactor[1] = 1;
        exrep(p, 2, n) {
            if(!isprime[p]) {
                continue;
            }
            minfactor[p] = p;
            mobius[p] = -1;
            for(ll q = 2*p; q <= n; q += p) {
                isprime[q] = 0;
                if(minfactor[q] == -1) {
                    minfactor[q] = p;
                }
                if((q / p) % p == 0) {
                    mobius[q] = 0;
                }
                else {
                    mobius[q] = -mobius[q];
                }
            }
        }
    }
    // 高速素因数分解。O(log(n))でnを素因数分解する
    vector<P> factorize(ll n) {  // (素因数, 指数) のvectorを返す
        vector<P> res;
        while(n > 1) {
            ll p = minfactor[n];
            ll i = 0;
            while(minfactor[n] == p) {
                n /= p;
                i++;
            }
            res.emplace_back(make_pair(p, i));
        }   
        return res;
    }
    // 高速約数列挙。O(σ(n))でnの約数を求める。σ(n)はnの約数の個数
    vl divisors(ll n) {
        vl res({1});
        auto pf = factorize(n);
        for(auto p : pf) {
            ll s = res.size();
            rep(i, s) {
                ll x = 1;
                rep(j, p.second) {
                    x *= p.first;
                    res.pb(res[i] * x);
                }
            }
        }
        return res;
    }
};
int main() {
    ll n;
    double p;
    cin >> n >> p;
    Eratosthenes e(n+1);
    double ans = 0.0;
    exrep(i, 2, n) {
        vl v = e.divisors(i);
        int m = v.size() - 2;
        if(m == 0) {
            ans += 1.0;
        }
        else {
            ans += pow(1.0 - p, m);
        }
    }
    exout(ans);
    re0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX