fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1000005;
  6.  
  7. int n, nxt[MAXN], mobius[MAXN];
  8. double f[MAXN], logFact[MAXN];
  9.  
  10. double logC(int n, int k) {
  11.     return logFact[n] - logFact[k] - logFact[n-k];
  12. }
  13.  
  14. double getGcdProbability(int d, int k) {
  15.     int cnt1 = n%d;
  16.     int cnt0 = d - cnt1;
  17.     int n0 = n / d;
  18.     int n1 = n0 + 1;
  19.  
  20.     double ans = 0;
  21.     if (n0 >= k)
  22.         //C(n0, k) * cnt0 / C(n, k)
  23.         ans += exp(logC(n0, k) - logC(n, k) + log(cnt0));
  24.     if (n1 >= k)
  25.         //C(n1, k) * cnt1 / C(n, k)
  26.         ans += exp(logC(n1, k) - logC(n, k) + log(cnt1));
  27.  
  28.     return ans;
  29. }
  30.  
  31. int main() {
  32.     n = 1000000;
  33.     for(int i = 2; i <= n; ++i) {
  34.         if (nxt[i] != 0)
  35.             continue;
  36.         for(int j = i; j <= n; j += i)
  37.             if (nxt[j] == 0)
  38.                 nxt[j] = i;
  39.     }
  40.  
  41.     for(int i = 1; i <= n; ++i) {
  42.         mobius[i] = 1;
  43.         int x = i;
  44.  
  45.         while (x > 1) {
  46.             int p = nxt[x], cnt = 0;
  47.             while (nxt[x] == p) {
  48.                 ++cnt;
  49.                 x /= p;
  50.             }
  51.  
  52.             if (cnt >= 2)
  53.                 mobius[i] = 0;
  54.             else
  55.                 mobius[i] *= -1;
  56.         }
  57.     }
  58.  
  59.     logFact[0] = 0;
  60.     for(int i = 1; i <= n; ++i)
  61.         logFact[i] = logFact[i-1] + log(i);
  62.  
  63.     for(int k = 2; k <= 30; ++k) {
  64.         double P = 0;
  65.         for(int i = 1; i <= n; ++i)
  66.             P += getGcdProbability(i, k) * mobius[i];
  67.  
  68.         printf("%d %.9g\n", k, 1 - P);
  69.     }
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.51s 38672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 0.999998001
3 0.392071074
4 0.168091284
5 0.0760606768
6 0.0356120528
7 0.0170470179
8 0.00827989868
9 0.00406064698
10 0.00200427473
11 0.00099353134
12 0.000493911528
13 0.000246006673
14 0.000122687068
15 6.12379315e-05
16 3.0583622e-05
17 1.52799444e-05
18 7.6359697e-06
19 3.81662555e-06
20 1.90784638e-06
21 9.53760751e-07
22 4.76822577e-07
23 2.38390116e-07
24 1.19187008e-07
25 5.95903042e-08
26 2.97938175e-08
27 1.48963248e-08
28 7.44789574e-09
29 3.7238217e-09
30 1.86184956e-09
https://ideone.com/IHmndY
1114E - Arithmetic Progression (Fail Probability Calculation)
language:
C++14 (gcc 8.3)
created:
5 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!