#line 2 "nt/sieve.hpp" #include #include namespace NT { struct Sieve { int N; std::vector primes; std::vector spf; std::vector phi; std::vector 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> get_prime_factors(int x) const { std::vector> 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 get_distinct_primes(int x) const { std::vector 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 get_all_divisors(int x) const { auto factors = get_prime_factors(x); std::vector 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 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; }