fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  8. typedef long long LL;
  9. typedef pair<int, int> PII;
  10.  
  11. bool pr[100100];
  12. vector<int> p;
  13. map<basic_string<int>, vector<double> > ma;
  14.  
  15. vector<double> solve(basic_string<int> &a);
  16.  
  17. vector<double> rec(basic_string<int> &a, vector<int> &cnt, int &times, int pos) {
  18.     if (pos == (int)a.size()) {
  19.         bool ok = false;
  20.         REP(i, cnt.size()) if (cnt[i] != 0) {
  21.             ok = true;
  22.             break;
  23.         }
  24.         if (!ok) return vector<double>();
  25.         ok = false;
  26.         REP(i, cnt.size()) if (cnt[i] != a[i]) {
  27.             ok = true;
  28.             break;
  29.         }
  30.         if (!ok) return vector<double>();
  31.         basic_string<int> b, c;
  32.         REP(i, a.size()) {
  33.             if (cnt[i] != 0) b += cnt[i];
  34.             if (a[i] != cnt[i]) c += a[i] - cnt[i];
  35.         }
  36.         sort(b.begin(), b.end());
  37.         sort(c.begin(), c.end());
  38.         vector<double> v1 = solve(b);
  39.         vector<double> v2 = solve(c);
  40.         if (v1.size() < v2.size()) swap(v1, v2);
  41.         v2.resize(v1.size());
  42.         for (int i = 1; i < (int)v1.size(); ++i) {
  43.             v1[i] += v1[i - 1];
  44.             v2[i] += v2[i - 1];
  45.         }
  46.         REP(i, v1.size()) v1[i] *= v2[i];
  47.         for (int i = (int)v1.size() - 1; i > 0; --i) {
  48.             v1[i] -= v1[i - 1];
  49.         }
  50.         ++times;
  51.         return v1;
  52.     }
  53.     vector<double> ret;
  54.     REP(i, a[pos] + 1) {
  55.         cnt[pos] = i;
  56.         vector<double> cur = rec(a, cnt, times, pos + 1);
  57.         if (ret.size() < cur.size()) ret.resize(cur.size());
  58.         REP(i, cur.size()) ret[i] += cur[i];
  59.     }
  60.     return ret;
  61. }
  62.  
  63. vector<double> solve(basic_string<int> &a) {
  64.     auto it = ma.find(a);
  65.     if (it != ma.end()) {
  66.         return it->second;
  67.     }
  68.     if ((int)a.size() == 1 && a[0] == 1) {
  69.         return ma[a] = vector<double>(1, 1.0);
  70.     }
  71.     vector<int> cnt(a.size());
  72.     int times = 0;
  73.     vector<double> res = rec(a, cnt, times, 0);
  74.     double di = 1.0 / times;
  75.     REP(i, res.size()) res[i] *= di;
  76.     res.resize(res.size() + 1);
  77.     for (int i = (int)res.size() - 1; i > 0; --i) res[i] = res[i - 1];
  78.     res[0] = 0;
  79.     return ma[a] = res;
  80. }
  81.  
  82. int main() {
  83.     //freopen("input.txt", "r", stdin);
  84.     REP(i, 100100) pr[i] = true;
  85.     pr[0] = pr[1] = false;
  86.     REP(i, 1000) if (pr[i]) {
  87.         for (int j = i * i; j < 100100; j += i) {
  88.             pr[j] = false;
  89.         }
  90.     }
  91.     REP(i, 100100) if (pr[i]) {
  92.         p.pb(i);
  93.     }
  94.     int tt;
  95.     scanf("%d", &tt);
  96.     REP(test, tt) {
  97.         LL x;
  98.         scanf("%lld", &x);
  99.         basic_string<int> a;
  100.         for (int i = 0; (LL)p[i] * p[i] <= x; ++i) if (x % p[i] == 0) {
  101.             x /= p[i];
  102.             int cnt = 1;
  103.             while (x % p[i] == 0) {
  104.                 x /= p[i];
  105.                 ++cnt;
  106.             }
  107.             a.pb(cnt);
  108.         }
  109.         if (x > 1) a.pb(1);
  110.         sort(a.begin(), a.end());
  111.         vector<double> res = solve(a);
  112.         double ans = 0;
  113.         REP(i, res.size()) ans += i * res[i];
  114.         printf("%.9f\n", ans);
  115.     }
  116.     return 0;
  117. }
Success #stdin #stdout 0s 3524KB
comments (?)
stdin 
3
3
12
48
stdout 
0.000000000
2.000000000
3.333333333
https://ideone.com/gJXUtq
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!