#include #include using namespace std; using namespace atcoder; istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); } istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } typedef long long ll; typedef vector> Graph; typedef pair pii; typedef pair pll; #define FOR(i,l,r) for (int i = l;i < (int)(r); i++) #define rep(i,n) for (int i = 0;i < (int)(n); i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define my_sort(x) sort(x.begin(), x.end()) #define my_max(x) *max_element(all(x)) #define my_min(x) *min_element(all(x)) 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) { if (a > b) { a = b; return 1; } return 0; } const int INF = (1<<30) - 1; const ll LINF = (1LL<<62) - 1; const int MOD = 998244353; const int MOD2 = 1e9+7; const double PI = acos(-1); vector di = {1,0,-1,0}; vector dj = {0,1,0,-1}; #ifdef LOCAL # include # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast(0)) #endif // https://qiita.com/drken/items/3beb679e54266f20ab63 struct Eratosthenes{ int N; vector isprime; vector minfactor, mobius; Eratosthenes(int N_max = 1e7){init(N_max);} //初期化 void init(int N_max = 1e7){ int N = N_max; isprime.assign(N+1,true); minfactor.assign(N+1,-1); mobius.assign(N+1,1); //Eratosthenes O(NloglogN) isprime[0] = false; isprime[1] = false; for(int p=2;p<=N;p++){ if (!isprime[p])continue; minfactor[p] = p; mobius[p] = -1; //pの倍数の処理 for(int q=2*p;q<=N;q+=p){ isprime[q] = false; if (minfactor[q] == -1){ minfactor[q] = p; } if ((q/p) % p == 0) mobius[q] = 0; else mobius[q] *= -1; } } } //素数判定,O(1) bool judge_prime(int num){ return isprime[num]; } //素数列挙,O(N) vector list_primes(int num = -1){ if (num == -1) num = N; vector primes; for(int p=0;p<=num;p++){ if (isprime[p]) primes.push_back(p); } return primes; } //高速素因数分解,O(logN),{(素因数,個数)...} vector factorize(int x){ vector ans; while(x > 1){ int p = minfactor[x]; int e = 0; while(minfactor[x] == p){ x /= p; e++; } ans.push_back(make_pair(p,e)); } return ans; } //高速約数列挙 O(240(N <= 1e6),1344(N <= 1e9)) vector divisors(int x){ vector ans; ans.push_back(1); vector facts = factorize(x); for(auto [p,e]:facts){ int s = ans.size(); for(int i=0;i mobius[n] = 0 //mobius[n] = pow(-1,Nの素数の種類) int my_mobius(int x){ return mobius[x]; } }; // f -> F, 累積和Fを求める template vector fast_zeta(vector &f){ vector res = f; int N = f.size() - 1; Eratosthenes er(N); for(int p=2;p<=N;p++){ if (!er.judge_prime(p)) continue; for(int k=(N/p);k>0;k--){ res[k] += res[k * p]; } } return res; } // // F -> f, 累積和Fを分解する // template // vector fast_mobius(vector &F){ // vector res = F; // int N = F.size() - 1; // Eratosthenes er(N); // for(int p=2;p<=N;p++){ // if (!er.judge_prime(p)) continue; // for(int k=1;k<=(N/p);k++){ // res[k] -= res[k * p]; // } // } // return res; // } template vector gcd_conv(vector &f, vector &g){ int N = max(f.size(), g.size()); vector F(N+1) , G(N+1), H(N+1); for(int i=0;i> L; Eratosthenes er(L); auto fast_mobius = [&](vector &A, int N){ for(int p=2;p<=N;p++){ if (!er.judge_prime(p)) continue; for(int k=1;k<=(N/p);k++){ A[k] -= A[k * p]; } } }; vector Ld = er.divisors(L); vector id(L + 1), inv(L + 1); rep(i, (int)Ld.size()){ id[Ld[i]] = i; inv[i] = Ld[i]; } int K = (int)Ld.size(); vector F(K, vector(L + 1)); vector memo(L + 1, -1); memo[1] = 0.0; function dp = [&](int x){ if(memo[x] >= 0.0) return memo[x]; auto divs = er.divisors(x); for(auto &M : divs) F[id[x]][M] = x / M; fast_mobius(F[id[x]], x); double acc = 0.0; for(auto &M : divs) { if(M == x || M == 1) continue; acc += (double)F[id[x]][M] * dp(M); } memo[x] = (acc + (double)x) / (double)(x - 1); return memo[x]; }; cout << fixed << setprecision(15) << dp(L) << endl; }