Tekijät

#include <bits/stdc++.h>
using namespace std;
int z[1010101];
int p[1010101];
int ma[1010101];
vector<int> pa[1010101];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int x[n];
  for (int i = 0; i < n; ++i) cin >> x[i], z[x[i]]++;
  for (int i = 2; i <= 1000000; ++i) {
    bool up = !p[i];
    for (int j = i; j <= 1000000; j += i) {
      p[j] = 1;
      if (up && z[j]) pa[j].push_back(i);
      ma[i] += z[j];
    }
  }
  long res = 0;
  for (int i = 0; i < n; ++i) {
    vector<int> &op = pa[x[i]];
    if (x[i] == 1) {
      res += n-1;
      continue;
    }
    int opc = op.size();
    long ores = 0;
    for (int m = 1; m < (1<<opc); ++m) {
      int y = 1;
      for (int j = 0; j < opc; ++j) if (m & (1<<j)) y *= op[j];
      long gs = ma[y];
      if (__builtin_parity(m)) ores += gs;
      else ores -= gs;
    }
    res += n-ores;
  }
  cout << res/2 << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 2, 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED

Test 6

Group: 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED