#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include using namespace std; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T &a, T b) { return ((a>b) ? (a = b, true) : (false));} #define rep(i,s,n) for(long long i=s;i<(long long)(n);i++) #define rrep(i,s,n) for(long long i=n-1;i>=s;i--) const long long inf = 1LL<<60; typedef long long ll; typedef long double ld; #define cmp [](pair a, pair b){return a.second P; typedef pair > PP; #define rll ll,vector,greater #define rP P,vector

,greater

const long double pi = 3.14159265358979; typedef unsigned long long ull; #define vll vector #define vvll vector> #define vvch vector> #define vch vector #define rPP PP,vector,greater #define vP vector

#define vvP vector> #define all(x) x.begin(), x.end() //bitの差集合 S & ~(1< isprime; // 整数 i を割り切る最小の素数 vector minfactor; //メビウス関数 //約数系包除に使用する //mobius[n] := nに同じ素因数が複数個ある => 0, nの素因数が奇数個 => -1, 素因数が偶数個 => 1 vector mobius; // コンストラクタで篩を回す Eratosthenes(ll N) : isprime(N+1, true), minfactor(N+1, -1), mobius(N+1, 1) { // 1 は予めふるい落としておく isprime[1] = false; minfactor[1] = 1; // 篩 for (ll p = 2; p <= N; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p についての情報更新 minfactor[p] = p; mobius[p] = -1; // p 以外の p の倍数から素数ラベルを剥奪 for (ll q = p * 2; q <= N; q += p) { // q は合成数なのでふるい落とす isprime[q] = false; // q は p で割り切れる旨を更新 if (minfactor[q] == -1) minfactor[q] = p; if((q/p) % p == 0) mobius[q] = 0; else mobius[q] = -mobius[q]; } } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector

factorize(ll n) { vector

res; while (n > 1) { ll p = minfactor[n]; ll exp = 0; // n で割り切れる限り割る while (minfactor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } return res; } // 高速約数列挙 vector divisors(ll n) { vector res({1}); // n を素因数分解 (メンバ関数使用) auto pf = factorize(n); // 約数列挙 for (auto p : pf) { ll s = (ll)res.size(); for (ll i = 0; i < s; ++i) { ll v = 1; for (ll j = 0; j < p.second; ++j) { v *= p.first; res.push_back(res[i] * v); } } } return res; } }; int main() { ll n; cin >> n; Eratosthenes er(n+1); map dp; dp[1] = 0; //nの約数のみを考えればよく、単純に昇順でいい auto divisors = er.divisors(n); sort(all(divisors)); for(auto divisor : divisors) { if(divisor == 1) continue; //cout << divisor << endl; auto sub_divisors = er.divisors(divisor); //divisorとのgcdについて全探索? sort(all(sub_divisors)); reverse(all(sub_divisors)); map cnt; //gcdがkeyとなるものの数 for(auto sub_divisor : sub_divisors) { cnt[sub_divisor] = n / sub_divisor; for(auto p : divisors) { if(p == 1) continue; if(p * sub_divisor > divisor) break; cnt[sub_divisor] -= cnt[p * sub_divisor]; } } ld sum = divisor; for(auto p : cnt) sum += dp[p.first] * p.second; dp[divisor] = sum / (ld)(divisor - 1); } cout << setprecision(20) << dp[n] << endl; }