fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4.  
  5. namespace solve {
  6.   const int N = 1000000 + 10;
  7.   std::vector<int> divs[N];
  8.   std::vector<std::pair<int, int>> edges[N];
  9.   int p[N], m;
  10.   int64 f[N], mu[N];
  11.   void init() {
  12.     for (int i = 1; i < N; ++i) {
  13.       for (int j = i; j < N; j += i) {
  14.         divs[j].push_back(i);
  15.       }
  16.     }
  17.     mu[1] = 1;
  18.     m = 0;
  19.     for (int i = 2; i < N; ++i) {
  20.       if(!p[i]) p[m++] = i, mu[i] = -1;
  21.       for (int j = 0; i * p[j] < N && j < m; ++j) {
  22.         p[i * p[j]] = 1;
  23.         if (i % p[j]) mu[i * p[j]] = -mu[i];
  24.         else {
  25.           mu[i * p[j]] = 0;
  26.           break;
  27.         }
  28.       }
  29.     }
  30.   }
  31.   void run(int n) {
  32.     for (int i = 1; i <= n; ++i) {
  33.       edges[i].clear();
  34.       f[i] = n / i;
  35.     }
  36.     int64 ret = 0, A = 0, B = 0;
  37.     for (int i = 1; i <= n; ++i) {
  38.       ret += mu[i] * f[i] * f[i] * f[i];
  39.       //cout<<"I:mu["<<i<<"] * f["<<i<<"] * f["<<i<<"] * f["<<i<<"]="<<mu[i] * f[i] * f[i] * f[i]<<endl;
  40.     }
  41.     std::vector<int> from, to, wei;
  42.     m = 0;
  43.     std::vector<int> deg(n + 1);
  44.     for (int i = 1; i <= n; ++i) {
  45.       if (!mu[i]) continue;
  46.       for (int j = i; j <= n; j += i) {
  47.         if (mu[j] && mu[j / i]) {
  48.           for (auto &&k: divs[j / i]) {
  49.             int x = i * k, y = j / k;
  50.             if (x >= y) continue;
  51.             deg[x]++;
  52.             deg[y]++;
  53.             B += (mu[x] * f[y] + mu[y] * f[x]) * f[j] * f[j];
  54.             // cout<<"3B:(mu["<<x<<"] * f["<<y<<"] + mu["<<y<<"] * f["<<x<<"]) * f["<<j<<"] * f["<<j<<"]="<<(mu[x] * f[y] + mu[y] * f[x]) * f[j] * f[j]<<endl;
  55.             from.push_back(x);
  56.             to.push_back(y);
  57.             wei.push_back(f[j]);
  58.             ++m;
  59.           }
  60.         }
  61.       }
  62.     }
  63.     for (int i = 0; i < m; ++i) {
  64.       int u = from[i], v = to[i], w = wei[i];
  65.       //cout<<u<<" "<<v<<" "<<w<<endl;
  66.       if (deg[u] < deg[v]) edges[u].emplace_back(v, w);
  67.       else edges[v].emplace_back(u, w);
  68.     }
  69.     std::vector<int> mark(n + 1, -1);int tri=0,n_edg=0;
  70.     for (int a = 1; a <= n; ++a) {
  71.       for (auto &&e: edges[a]) mark[e.first] = e.second;
  72.       for (auto &&e: edges[a]) {n_edg++;
  73.         int b = e.first, w1 = e.second;
  74.         for (auto &&ee: edges[b]) {
  75.           int c = ee.first, w2 = ee.second;
  76.           if (mark[c] != -1) {
  77.             A += mu[a] * mu[b] * mu[c] * w1 * w2 * mark[c];
  78.             // cout<< "w2=" << w2 << " mark[c]=" << mark[c]<<endl;
  79.             // cout<<"6A:mu["<<a<<"] * mu["<<b<<"] * mu["<<c<<"] * "<<w1<<" * "<<w2<<" * mark["<<c<<"]="<<mu[a] * mu[b] * mu[c] * w1 * w2 * mark[c]<<endl;
  80.             tri++;
  81.           }
  82.         }
  83.       }
  84.       for (auto &&e: edges[a]) {mark[e.first] = -1;
  85. 	      //cout<<"a="<<a<<" e(f,s)=("<<e.first<<","<<e.second<<")"<<endl;
  86.       }
  87.     }
  88.     ret += A * 6 + B * 3;
  89.     // printf("%lld\n", ret);
  90.     cout<<n<<" "<<n_edg<<" "<<pow(n_edg,1.5)<<" "<<tri<<" "<<pow(n_edg,1.5)/tri<<endl;
  91.   }
  92. }
  93.  
  94. int main() {
  95.   solve::init();
  96.   int n;
  97.   //scanf("%d", &n);
  98.   for(int n=999999;n<=1000000;n++)
  99.   solve::run(n);
  100.   return 0;
  101. }
  102.  
Success #stdin #stdout 9.81s 447692KB
comments (?)
stdin
copy 
6
stdout
copy 
999999 10010249 3.16714e+10 436654181 72.532
1000000 10010249 3.16714e+10 436654181 72.532
https://ideone.com/jTDLB2
language:
C++ (gcc 8.3)
created:
3 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!