結果
| 問題 | No.144 エラトステネスのざる |
| ユーザー |
 tk
|
| 提出日時 | 2023-04-20 00:37:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 56 ms / 2,000 ms |
| コード長 | 9,062 bytes |
| コンパイル時間 | 1,791 ms |
| コンパイル使用メモリ | 198,856 KB |
| 最終ジャッジ日時 | 2025-02-12 10:27:27 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#line 1 "library/template/template.hpp"#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using ull = unsigned long long;using uint = unsigned;using vll = vector<ll>;using pii = pair<int, int>;using pll = pair<ll, ll>;using pdd = pair<ld, ld>;using tuplis = array<ll, 3>;template <class T>using pq = priority_queue<T, vector<T>, greater<T>>;const ll LINF = 0x1fffffffffffffff;const ll MINF = 0x7fffffffffff;const int INF = 0x3fffffff;const int MOD = 1000000007;const int MODD = 998244353;const ld DINF = numeric_limits<ld>::infinity();const ld EPS = 1e-9;const ld PI = 3.1415926535897932;const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};#define overload5(a, b, c, d, e, name, ...) name#define overload4(a, b, c, d, name, ...) name#define overload3(a, b, c, name, ...) name#define rep1(n) for (ll i = 0; i < n; ++i)#define rep2(i, n) for (ll i = 0; i < n; ++i)#define rep3(i, a, b) for (ll i = a; i < b; ++i)#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define rrep1(n) for (ll i = n; i--;)#define rrep2(i, n) for (ll i = n; i--;)#define rrep3(i, a, b) for (ll i = b; i-- > (a);)#define rrep4(i, a, b, c) for (ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)#define each1(i, a) for (auto &&i : a)#define each2(x, y, a) for (auto &&[x, y] : a)#define each3(x, y, z, a) for (auto &&[x, y, z] : a)#define each4(w, x, y, z, a) for (auto &&[w, x, y, z] : a)#define each(...) overload5(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)#define all1(i) begin(i), end(i)#define all2(i, a) begin(i), begin(i) + a#define all3(i, a, b) begin(i) + a, begin(i) + b#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)#define rall1(i) rbegin(i), rend(i)#define rall2(i, a) rbegin(i), rbegin(i) + a#define rall3(i, a, b) rbegin(i) + a, rbegin(i) + b#define rall(...) overload3(__VA_ARGS__, rall3, rall2, rall1)(__VA_ARGS__)#define sum(...) accumulate(all(__VA_ARGS__), 0LL)#define dsum(...) accumulate(all(__VA_ARGS__), 0.0L)#define Msum(...) accumulate(all(__VA_ARGS__), Modint{})#define elif else if#define INT(...) \int __VA_ARGS__; \in(__VA_ARGS__)#define LL(...) \ll __VA_ARGS__; \in(__VA_ARGS__)#define ULL(...) \ull __VA_ARGS__; \in(__VA_ARGS__)#define STR(...) \string __VA_ARGS__; \in(__VA_ARGS__)#define CHR(...) \char __VA_ARGS__; \in(__VA_ARGS__)#define DBL(...) \double __VA_ARGS__; \in(__VA_ARGS__)#define LD(...) \ld __VA_ARGS__; \in(__VA_ARGS__)#define vec(type, name, ...) vector<type> name(__VA_ARGS__)#define VEC(type, name, size) \vector<type> name(size); \in(name)#define vv(type, name, h, ...) vector name(h, vector<type>(__VA_ARGS__))#define VV(type, name, h, w) \vector name(h, vector<type>(w)); \in(name)#define vvv(type, name, h, w, ...) vector name(h, vector(w, vector<type>(__VA_ARGS__)))template <class T>auto min(const T &a){return *min_element(all(a));}template <class... Ts>void in(Ts &...t);[[maybe_unused]] void print() {}template <class T, class... Ts>void print(const T &t, const Ts &...ts);template <class... Ts>void out(const Ts &...ts){print(ts...);cout << '\n';}namespace IO{#define VOID(a) decltype(void(a))struct S{S(){cin.tie(nullptr)->sync_with_stdio(0);fixed(cout).precision(12);}} S;template <int I>struct P : P<I - 1>{};template <>struct P<0>{};template <class T>void i(T &t) { i(t, P<3>{}); }void i(vector<bool>::reference t, P<3>){int a;i(a);t = a;}template <class T>auto i(T &t, P<2>) -> VOID(cin >> t) { cin >> t; }template <class T>auto i(T &t, P<1>) -> VOID(begin(t)){for (auto &&x : t)i(x);}template <class T, size_t... idx>void ituple(T &t, index_sequence<idx...>) { in(get<idx>(t)...); }template <class T>auto i(T &t, P<0>) -> VOID(tuple_size<T>{}) { ituple(t, make_index_sequence<tuple_size<T>::value>{}); }template <class T>void o(const T &t) { o(t, P<4>{}); }template <size_t N>void o(const char (&t)[N], P<4>) { cout << t; }template <class T, size_t N>void o(const T (&t)[N], P<3>){o(t[0]);for (size_t i = 1; i < N; i++){o(' ');o(t[i]);}}template <class T>auto o(const T &t, P<2>) -> VOID(cout << t) { cout << t; }template <class T>auto o(const T &t, P<1>) -> VOID(begin(t)){bool first = 1;for (auto &&x : t){if (first)first = 0;elseo(' ');o(x);}}template <class T, size_t... idx>void otuple(const T &t, index_sequence<idx...>) { print(get<idx>(t)...); }template <class T>auto o(T &t, P<0>) -> VOID(tuple_size<T>{}) { otuple(t, make_index_sequence<tuple_size<T>::value>{}); }#undef VOID}#define unpack(a) \(void)initializer_list<int> \{ \(a, 0)... \}template <class... Ts>void in(Ts &...t){unpack(IO::i(t));}template <class T, class... Ts>void print(const T &t, const Ts &...ts){IO::o(t);unpack(IO::o((cout << ' ', ts)));}#undef unpack#ifdef DEBUGll __lg(ull x){return 63 - __builtin_clzll(x);}#define debug(...) \{ \print(#__VA_ARGS__); \print(":"); \out(__VA_ARGS__); \}#else#define debug(...) void(0)#endif#define YESNO(yes, no) \void yes(bool i = 1) \{ \out(i ? #yes : #no); \} \void no() \{ \out(#no); \}YESNO(first, second)YESNO(First, Second)YESNO(Yes, No)YESNO(YES, NO)YESNO(possible, impossible)YESNO(POSSIBLE, IMPOSSIBLE)template <class... T>constexpr auto min(T... a){return min(initializer_list{a...});}ll mod_abs(ll a, ll mod){if (a < 0)return a + mod;return a % mod;}template <typename T>map<T, ll> counter(vector<T> a){map<T, ll> res;rep(a.size()){if (res.count(a[i]) == 0)res[a[i]] = 1;elseres[a[i]]++;}return res;}#line 1 "library/math/modpow.hpp"ll modpow(ll a, ll b, ll p){ll res = 1;while (b){if (b & 1)res = (res * a) % p;a = (a * a) % p;b /= 2;}return res;}#line 1 "library/math/combinatorics/combination.hpp"struct Combination{ll size;ll mod;ll f = 1;vector<ll> fac = {f};vector<ll> facinv;Combination(ll size, ll p){mod = p;rep(i, 1, size + 1){f = f * i % mod;fac.push_back(f);}f = modpow(f, mod - 2, mod);facinv.push_back(f);for (ll i = size; i > 0; i--){// out(i);f = f * i % mod;facinv.push_back(f);}reverse(all(facinv));}ll c(ll n, ll r){if (!(0 <= r && r <= n))return 0;return (((fac[n] * facinv[r]) % mod) * facinv[n - r]) % mod;}};#line 2 "library/graph/graph-template/graph-template.hpp"template <typename T>struct Edge{ll from;ll to;T cost;bool operator<(const Edge &o) const{return cost < o.cost;}};#line 2 "library/graph/dijkstra.hpp"template <typename T>vector<T> dijkstra(vector<vector<Edge<T>>> g, ll s, ll v){vector<ll> before(v, -1);vector<T> dist(v, LINF);vector<bool> seen(v, false);dist[s] = 0;priority_queue<pair<ll, T>, vector<pair<ll, T>>, greater<pair<ll, T>>> q;q.push(pair(0, s));while (!q.empty()){auto top = q.top().second;q.pop();seen[top] = true;for (Edge<ll> next : g[top]){if (!seen[next.to] && dist[top] + next.cost < dist[next.to]){before[next.to] = top;dist[next.to] = dist[top] + next.cost;q.push(pair(dist[next.to], next.to));}}}return dist;}#line 1 "library/structure/union-find.hpp"struct UnionFind{vector<ll> p;UnionFind(size_t sz) : p(sz, -1) {}ll find(ll x){if (p[x] < 0)return x;return p[x] = find(p[x]);}void unite(ll x, ll y){ll xp = find(x);ll yp = find(y);if (xp == yp)return;if (p[xp] > p[yp])swap(x, y);p[xp] += p[yp];p[yp] = xp;}ll size(ll x){return -p[find(x)];}};#line 3 "library/graph/kruskal.hpp"template <typename T>T kruskal(vector<Edge<T>> g, ll n){sort(all(g));UnionFind uf(n);ll cost = 0;rep(g.size()){auto e = g[i];if (uf.find(e.from) != uf.find(e.to)){cost += e.cost;uf.unite(e.from, e.to);}}return cost;}#line 7 "main.cpp"int main(){vector<ll> divisors(2000000);ll n;double p;double res = 0;cin >> n >> p;rep(i, 2, n + 1){rep(j, i, n + 1, i){divisors[j]++;}res += pow(1 - p, divisors[i] - 1);}out((double)res);}