結果
| 問題 | No.144 エラトステネスのざる |
| ユーザー |
 hamray
|
| 提出日時 | 2020-02-11 16:25:26 |
| 言語 | C++11 (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 54 ms / 2,000 ms |
| コード長 | 9,040 bytes |
| コンパイル時間 | 1,361 ms |
| コンパイル使用メモリ | 167,336 KB |
| 実行使用メモリ | 7,644 KB |
| 最終ジャッジ日時 | 2024-10-01 08:03:47 |
| 合計ジャッジ時間 | 2,356 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:344:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
344 | int N; scanf("%d", &N);
| ~~~~~^~~~~~~~~~
main.cpp:345:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
345 | double p; scanf("%lf", &p);
| ~~~~~^~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>//typedef//-------------------------#include <bits/stdc++.h>#define M_PI 3.14159265358979323846using namespace std;//conversion//------------------------------------------inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }inline int readInt() { int x; scanf("%d", &x); return x; }//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<long long, long long> PLL;typedef pair<int, PII> TIII;typedef long long LL;typedef unsigned long long ULL;typedef vector<LL> VLL;typedef vector<VLL> VVLL;//container util//------------------------------------------#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define SQ(a) ((a)*(a))#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)#define EXIST(s,e) ((s).find(e)!=(s).end())#define SORT(c) sort((c).begin(),(c).end())//repetition//------------------------------------------#define FOR(i,s,n) for(int i=s;i<(int)n;++i)#define REP(i,n) FOR(i,0,n)#define MOD 1000000007#define rep(i, a, b) for(int i = a; i < (b); ++i)#define trav(a, x) for(auto& a : x)#define all(x) x.begin(), x.end()#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;const double EPS = 1E-8;#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)class UnionFind {public:vector <ll> par;vector <ll> siz;vector <ll> maxv;UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {for (ll i = 0; i < sz_; ++i) par[i] = i;}void init(ll sz_) {par.resize(sz_);siz.assign(sz_, 1LL);for (ll i = 0; i < sz_; ++i) par[i] = i;}ll root(ll x) {while (par[x] != x) {x = par[x] = par[par[x]];}return x;}bool merge(ll x, ll y) {x = root(x);y = root(y);if (x == y) return false;if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(ll x, ll y) {return root(x) == root(y);}ll size(ll x) {return siz[root(x)];}};ll mod_pow(ll x, ll n, ll mod){ll res = 1;while(n){if(n&1) res = (res * x)%mod;res %= mod;x = x * x %mod;n >>= 1;}return res;}#define SIEVE_SIZE 5000000+10bool sieve[SIEVE_SIZE];void make_sieve(){for(int i=0; i<SIEVE_SIZE; ++i) sieve[i] = true;sieve[0] = sieve[1] = false;for(int i=2; i*i<SIEVE_SIZE; ++i) if(sieve[i]) for(int j=2; i*j<SIEVE_SIZE; ++j) sieve[i*j] = false;}bool isprime(ll n){if(n == 0 || n == 1) return false;for(ll i=2; i*i<=n; ++i) if(n%i==0) return false;return true;}const int MAX = 2000010;long long fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 二項係数計算long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}long long extGCD(long long a, long long b, long long &x, long long &y) {if (b == 0) {x = 1;y = 0;return a;}long long d = extGCD(b, a%b, y, x);y -= a/b * x;return d;}// 負の数にも対応した mod (a = -11 とかでも OK)inline long long mod(long long a, long long m) {return (a % m + m) % m;}// 逆元計算 (ここでは a と m が互いに素であることが必要)long long modinv(long long a, long long m) {long long x, y;extGCD(a, m, x, y);return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので}ll GCD(ll a, ll b){if(b == 0) return a;return GCD(b, a%b);}struct LazySegmentTree {private:int n;vector<ll> node, lazy;public:LazySegmentTree(vector<ll> v) {int sz = (int)v.size();n = 1; while(n < sz) n *= 2;node.resize(2*n-1);lazy.resize(2*n-1, 0);for(int i=0; i<sz; i++) node[i+n-1] = v[i];for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];}void eval(int k, int l, int r) {if(lazy[k] != 0) {node[k] += lazy[k];if(r - l > 1) {lazy[2*k+1] += lazy[k] / 2;lazy[2*k+2] += lazy[k] / 2;}lazy[k] = 0;}}void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a) return;if(a <= l && r <= b) {lazy[k] += (r - l) * x;eval(k, l, r);}else {add(a, b, x, 2*k+1, l, (l+r)/2);add(a, b, x, 2*k+2, (l+r)/2, r);node[k] = node[2*k+1] + node[2*k+2];}}ll getsum(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a) return 0;if(a <= l && r <= b) return node[k];ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);return vl + vr;}};int const INF = INT_MAX;struct SegmentTree {private:int n;vector<int> node;public:SegmentTree(vector<int> v) {int sz = v.size();n = 1; while(n < sz) n *= 2;node.resize(2*n-1, INF);for(int i=0; i<sz; i++) node[i+n-1] = v[i];for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]);}void update(int x, int val) {x += (n - 1);node[x] = val;while(x > 0) {x = (x - 1) / 2;node[x] = min(node[2*x+1], node[2*x+2]);}}int getmin(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;if(r <= a || b <= l) return INF;if(a <= l && r <= b) return node[k];int vl = getmin(a, b, 2*k+1, l, (l+r)/2);int vr = getmin(a, b, 2*k+2, (l+r)/2, r);return min(vl, vr);}};using Weight = int;using Flow = int;struct Edge {int src, dst;Weight weight;Flow cap;Edge() : src(0), dst(0), weight(0) {}Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}};using Edges = std::vector<Edge>;using Graph = std::vector<Edges>;using Array = std::vector<Weight>;using Matrix = std::vector<Array>;void add_edge(Graph &g, int a, int b, Weight w = 1) {g[a].emplace_back(a, b, w);g[b].emplace_back(b, a, w);}void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }// template<typename T> class basic_stopwatch: T {// typedef typename T BaseTimer;// public:// explicit basic_stopwatch(bool start);// explicit basic_stopwatch(char const* activity = "Stopwatch", bool start = true);// basic_stopwatch(std::ostream& log, char const* activity = "Stopwatch", bool start = true);// basic_stopwatch();// unsigned LapGet() const;// bool IsStarted() const;// unsigned Show(char const* event = "show");// unsigned Start(char const* event_name = "start");// unsigned Stop(char const* event_name = "stop");// private:// char const* m_activity;// unsigned m_lap;// std::ostream& m_log;// };// #include <chrono>// using namespace std::chrono;// class TimerBase {// public:// // タイマをクリアする// TimerBase(): m_start(system_clock::time_point::min()) {}// void Clear(){// m_start = system_clock::time_point::min();// }// bool IsStarted() const {// return (m_start.time_since_epoch() != system_clock::duration(0));// }// void Start() {// m_start = system_clock::now();// }// unsigned long GetMs(){// if(IsStarted()) {// system_clock::duration diff;// diff = system_clock::now() - m_start;// return (unsigned)(duration_cast<milliseconds>(diff).const();// }// return 0;// }// private:// system_clock::time_point m_start;// };int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);int N; scanf("%d", &N);double p; scanf("%lf", &p);double ans = 0.0;vector<int> fac(N+1, 0);for(int i=2; i<=N; i++){ans += pow(1-p, fac[i]);for(int j=i*2; j<=N; j+=i) {fac[j]++;}}printf("%.8lf\n", ans);return 0;}