// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/0144 #include #include #include #include #include #include #include #include /** * @brief 素数ライブラリ * * @tparam N */ template struct prime_number { prime_number() : is_not_prime(), data() { init(); } /** * @brief 素数判定 * * @param n * @return bool */ bool is_prime(std::int64_t n) const { assert(n >= 0); if (n < N) return !is_not_prime[n]; for (auto i : data) { if ((std::int64_t)i * i > n) break; if (n % i == 0) return false; } return true; } std::vector prime_numbers(int x) const { std::vector res; for (auto i : data) { if (i > x) break; res.emplace_back(i); } return res; } /** * @brief 素因数分解 * * @tparam T * @param x * @return std::vector> */ template std::vector> prime_factorization(T x) const { if (x == 1) return std::vector>(); std::vector> res; for (auto p : data) { int cnt = 0; for (; x % p == 0; x /= p) ++cnt; if (cnt) res.emplace_back(p, cnt); if ((std::int64_t)p * p > x) break; } if (x != 1) res.emplace_back(x, 1); return res; } /** * @brief 約数列挙 * * @tparam T * @param x * @return std::vector */ template std::vector divisors(T x) const { if (x == 1) return std::vector(1, 1); auto v = prime_factorization(x); std::vector res; res.emplace_back(1); for (auto p : v) { int n = res.size(); res.resize(n * (p.second + 1)); for (int i = 0; i < n * p.second; ++i) res[n + i] = res[i] * p.first; for (int i = 1; i <= p.second; ++i) { std::inplace_merge(res.begin(), res.begin() + n * i, res.begin() + n * (i + 1)); } } return res; } /** * @brief 因数分解列挙 * * @tparam T * @param x * @return std::vector> */ template std::vector> factorization(T x) const { std::vector> res; auto f = [&](auto self, std::vector v, T a) -> void { if (a == 1) res.emplace_back(v); for (auto i : this->divisors(a)) { if (i == 1 || (!v.empty() && v.back() > i)) continue; v.emplace_back(i); self(self, v, a / i); v.pop_back(); } }; f(f, std::vector(), x); return res; } private: std::bitset is_not_prime; std::vector data; void init() { is_not_prime[0] = is_not_prime[1] = true; for (int i = 2; i < N; ++i) { if (!is_not_prime[i]) { data.emplace_back(i); if ((std::int64_t)i * i >= N) continue; if (i == 2) { for (int j = i * i; j < N; j += i) is_not_prime[j] = true; } else { for (int j = i * i; j < N; j += i << 1) is_not_prime[j] = true; } } } } }; #ifdef ATCODER #pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2") #endif #pragma GCC optimize("Ofast,fast-math,unroll-all-loops") #include #ifndef ATCODER #pragma GCC target("sse4.2,avx2,bmi2") #endif template constexpr bool chmax(T &a, const U &b) { return a < (T)b ? a = (T)b, true : false; } template constexpr bool chmin(T &a, const U &b) { return (T)b < a ? a = (T)b, true : false; } constexpr std::int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr double EPS = 1e-7; constexpr double PI = 3.14159265358979323846; struct Sonic { Sonic() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(20); } constexpr void operator()() const {} } sonic; prime_number pn; int main(void) { int n; double p; std::cin >> n >> p; std::vector v(100000, 1); for (int i = 0; i < 99999; ++i) v[i + 1] = v[i] * (1 - p); double ans = 0; for (int x = 2; x <= n; ++x) { auto u = pn.divisors(x); ans += v[u.size() - 2]; } std::cout << ans << '\n'; return 0; }