fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5. vector<int> lp(N);
  6. vector<bool> p(N, 1);
  7. vector<vector<int>> pf(N), divisor(N);
  8.  
  9. int precompute() {
  10.   iota(lp.begin(), lp.end(), 0);
  11.   for (int i = 2; i < N; i++) {
  12.     if (p[i]) {
  13.       for (int j = i; j < N; j += i) {
  14.         lp[j] = min(lp[j], i);
  15.         if (i ^ j) p[j] = 0;
  16.       }
  17.     }
  18.   }
  19.   for (int i = 2; i < N; i++) {
  20.     for (int j = i; j < N; j += i) {
  21.       divisor[j].emplace_back(i);
  22.     }
  23.   }
  24.  
  25.   for (int i = 2; i < N; i++) {
  26.     int x = i;
  27.     while (lp[x] > 1) {
  28.       int t = lp[x];
  29.       pf[i].push_back(t);
  30.       while (x % t == 0) {
  31.         x /= t;
  32.       }
  33.     }
  34.   }
  35.   return 0;
  36. } 
  37.  
  38. int pre = precompute();
  39.  
  40.  
  41. int main() {
  42.   cin.tie(0)->sync_with_stdio(0);
  43.  
  44.   int n;
  45.   cin >> n;
  46.   vector<int> A(n);
  47.   for (int& x : A) cin >> x;
  48.  
  49.   vector<int> cnt(N);
  50.   for (int i = 0; i < n; i++) {
  51.     for (int d : divisor[A[i]]) cnt[d]++;
  52.   }
  53.   vector<int> ans(n);
  54.   for (int i = 0; i < n; i++) {
  55.     vector<int> pr;
  56.     for (int p : pf[A[i]]) pr.emplace_back(p);
  57.     for (int d : divisor[A[i]]) cnt[d]--;
  58.  
  59.     int k = pr.size();
  60.  
  61. 	// inclusion exclusion
  62.     for (int mask = 1; mask < 1 << k; mask++) {
  63.       int prod = 1;
  64.       for (int bit = 0; bit < k; bit++) {
  65.         if (mask >> bit & 1) prod *= pr[bit];
  66.       }
  67.       if (__builtin_popcount(mask) & 1) {
  68.         ans[i] += cnt[prod];
  69.       } else {
  70.         ans[i] -= cnt[prod];
  71.       }
  72.     }
  73.     for (int d : divisor[A[i]]) cnt[d]++;
  74.   }
  75.   for (int x : ans) cout << x << ' ';
  76.   return 0;
  77. }
Success #stdin #stdout 0.08s 19208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0 0 0 0 0
https://ideone.com/YCHh96
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!