fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define pb emplace_back
  5. #define mp make_pair
  6. #define fi first
  7. #define se second
  8. #define all(v) v.begin(), v.end()
  9.  
  10. set<int> fun(int n)
  11. {
  12.      set<int> v;
  13.      for (int i = 1; i <= sqrt(n); i++)
  14.      {
  15.           if (n % i == 0)
  16.           {
  17.                if (n / i == i)
  18.                     v.insert(i);
  19.  
  20.                else
  21.                {
  22.                     v.insert(i);
  23.                     v.insert(n / i);
  24.                }
  25.           }
  26.      }
  27.  
  28.      return v;
  29. }
  30.  
  31. signed main()
  32. {
  33.  
  34.      int t = 1;
  35.  
  36.      while (t--)
  37.      {
  38.  
  39.           int n, i, x, y, j, k;
  40.  
  41.           cin >> n;
  42.  
  43.           map<int, int> mm;
  44.  
  45.           vector<int> a(n, 0);
  46.           vector<pair<int, int>> v;
  47.  
  48.           for (i = 0; i < n; i++)
  49.           {
  50.                cin >> a[i];
  51.                v.pb(mp(a[i], i));
  52.                mm[a[i]]++;
  53.           }
  54.  
  55.           sort(all(v));
  56.           int mx = 1e5 + 9;
  57.           int h[mx] = {0};
  58.           int vis[mx] = {0};
  59.  
  60.           for (i = n - 1; i >= 0; i--)
  61.           {
  62.                if (vis[v[i].fi] == 0)
  63.                {
  64.                     vis[v[i].fi] = 1;
  65.                     x = v[i].fi;
  66.  
  67.                     set<int> p = fun(x);
  68.  
  69.                     for (int yy : p)
  70.                     {
  71.                          if (yy != x)
  72.                          {
  73.                               h[yy] += mm[x] + min(mm[yy] - 1, (int)0 );
  74.                               h[x] += mm[yy];
  75.                          }
  76.                     }
  77.                     h[x] += mm[x] - 1;
  78.                }
  79.           }
  80.  
  81.           for (i = 0; i < n; i++)
  82.           {
  83.                cout << h[a[i]] << " ";
  84.           }
  85.      }
  86. }
Success #stdin #stdout 0.01s 5580KB
comments (?)
stdin
copy 
5
6 6 6 6 6
stdout
copy 
4 4 4 4 4
https://ideone.com/H2Jlkn
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

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!