Shared code

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define MAXX 1000005

ll n;

ll sieve[MAXX];
ll withdiv[MAXX];
ll gcdpairs[MAXX];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  // sieve[i] = smallest prime number that is a divisor of i
  memset(sieve, -1, sizeof(sieve));
  for (ll i = 2; i < MAXX; ++i) {
    for (ll j = i; j < MAXX; j += i) {
      if (sieve[j] == -1) {
        sieve[j] = i;
      }
    }
  }

  cin >> n;
  vector<ll> a(n);
  for (auto &i : a) {
    cin >> i;
    ll x = i;
    map<ll, ll> m;
    while (x != 1) {
      ++m[sieve[x]];
      x /= sieve[x];
    }
    queue<ll> q;
    q.push(1);
    for (auto &i : m) {
      queue<ll> nq;
      while (!q.empty()) {
        ll fac = q.front();
        q.pop();
        for (ll j = 0, mul = 1; j <= i.second; ++j, mul *= i.first) {
          nq.push(fac * mul);
        }
      }
      q = nq;
    }
    while (!q.empty()) {
      ll fac = q.front();
      q.pop();
      ++withdiv[fac];
    }
  }

  for (ll i = MAXX - 1; i >= 1; --i) {
    gcdpairs[i] = withdiv[i] * (withdiv[i] - 1) / 2;
    for (ll j = 2 * i; j < MAXX; j += i) {
      gcdpairs[i] -= gcdpairs[j];
    }
  }

  cout << gcdpairs[1] << "\n";
}