/* -*- coding: utf-8 -*- * * 2829.cc: No.2829 GCD Divination - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_N = 10000000; const int MAX_P = 3200; /* typedef */ using vi = vector; using vb = vector; using vd = vector; /* global variables */ vb primes; vi pnums; /* subroutines */ int gen_primes(int maxp) { primes.assign(maxp + 1, true); primes[0] = primes[1] = false; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums.push_back(p); for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums.push_back(p); return (int)pnums.size(); } bool prime_decomp(int n, vi &ps, vi &ds) { ps.clear(), ds.clear(); for (auto pi: pnums) { if (pi * pi > n) { if (n > 1) ps.push_back(n), ds.push_back(1); return true; } if (n % pi == 0) { int fi = 0; while (n % pi == 0) n /= pi, fi++; ps.push_back(pi), ds.push_back(fi); } } return false; } void decomp_ps(int n, vi &ps, vi &ds) { ds.clear(); for (auto p: ps) { int fi = 0; while (n % p == 0) fi++, n /= p; ds.push_back(fi); } } int calc(vi &ds0, vi &ds1, vi &nds) { int p = 1, k = ds0.size(); for (int i = 0; i < k; i++) if (ds0[i] == ds1[i]) p *= nds[i] - ds1[i] + 1; return p; } void printv(vi &v) { for (auto a: v) printf(" %d", a); putchar('\n'); } /* main */ int main() { gen_primes(MAX_P); int n; scanf("%d", &n); vi ps, nds; prime_decomp(n, ps, nds); int k = ps.size(); //printf("ps="), printv(ps), printf("nds="), printv(nds); vi as; for (int p = 1; p * p <= n; p++) if (n % p == 0) { as.push_back(p); int q = n / p; if (q != p) as.push_back(q); } sort(as.begin(), as.end()); int m = as.size(); //printf("as="), printv(as); vector ads(m); for (int i = 0; i < m; i++) decomp_ps(as[i], ps, ads[i]); vd es(m, 0.0); vi ss(m); for (int i = 1; i < m; i++) { int sum = 0; for (int j = 1; j <= i; j++) sum += (ss[j] = calc(ads[j], ads[i], nds)); ss[0] = n - sum; //printf("n=%d, sum=%d\nss=", n, sum); //for (int j = 0; j <= i; j++) printf(" %d", ss[j]); putchar('\n'); // e[n] = 1 + e[0]*ss[0]/n+e[1]*ss[1]/n+...+e[n]*ss[n]/n // -> e[n](n-ss[n]) = n + e[0]*ss[0]+e[1]*ss[1]+..+e[n-1]*ss[n-1] double esum = 0.0; for (int j = 0; j < i; j++) esum += es[j] * ss[j]; es[i] = (n + esum) / (n - ss[i]); } printf("%.10lf\n", es[m - 1]); //for (int i = 0; i < m; i++) // printf(" es[%d] = %lf\n", as[i], es[i]); return 0; }