#line 1 "playground_A.cpp" #include #include #include #include using namespace std; using ll = long long; template inline bool chmax(T& a, const T& b) {if (a inline bool chmin(T& a, const T& b) {if (b namespace multiple { // 倍数についてのゼータ変換。 g_n = \Sigma_{n|m} f_m なる g を求める。 // n|mというのは、m%n==0という意味。 // O(N log N) (調和級数) // うまくやるとO(Nlog(log(N)))にできることがよく知られているが、難しいしlogは定数なので妥協する。 template std::vector zeta_transform_naive(const std::vector& f) { int N = f.size() - 1; std::vector g = f; for (int i = 1; i <= N; i++) { for (int j = 2 * i; j <= N; j += i) { g[i] = op(g[i], f[j]); } } return g; } // 倍数についてのメビウス変換 // f_n = \Sigma_{n|m} g_m なる g を求める。 // O(N log N) (調和級数) template std::vector moebius_transform_naive(const std::vector& f) { int N = f.size() - 1; std::vector g = f; for (int i = N; i >= 1; i--) { for (int j = 2 * i; j <= N; j += i) { g[i] = invop(g[i], g[j]); } } return g; } template std::map zeta_transform(const std::map& mp) { std::map ret = mp; for (std::pair pit : ret) { for (auto p2itr = ret.rbegin(); (*p2itr).first != pit.first; p2itr++) { if ((*p2itr).first % pit.first == 0) { ret[pit.first] = op(ret[pit.first], (*p2itr).second); } } } return ret; } template std::map moebius_transform(const std::map& mp) { std::map ret = mp; for (auto p1itr = ret.rbegin(); p1itr != ret.rend(); p1itr++) { for (auto p2itr = ret.rbegin(); p2itr != p1itr; p2itr++) { if ((*p2itr).first % (*p1itr).first == 0) { (*p1itr).second = invop((*p1itr).second, (*p2itr).second); } } } return ret; } } // namespace multiple #line 15 "playground_A.cpp" ll llpow(ll a, ll power) { ll ret =1; ll base =a; while (power > 0) { if (power & 1) { ret *= base; } base *= base; power >>= 1; } return ret; } ll op(ll a, ll b) {return a+b;} ll invop(ll a, ll b) {return a-b;} int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll N; cin >> N; map memo; memo[1] = 0.0; auto solve = [&memo] (auto self, ll n) -> double { if (memo.contains(n)) return memo.at(n); double divsum = 0; map g; for (int d=1; d*d <= n; d++) { if (n % d == 0) { g[d] = n/d; if (d != n/d) { g[n/d] = d; } } } mapf = multiple::moebius_transform(g); for (int d=2; d*d <= n; d++) { if (n % d == 0) { divsum += self(self, d) * f[d]; if (d != n/d) { divsum += self(self, n/d) * f[n/d]; } } } double ret = double(n) / double(n-1) + divsum / double(n-1); memo[n] = ret; return ret; }; cout << fixed << setprecision(10); cout << solve(solve,N) << endl; return 0; }