Tekijät

input/code.cpp:1:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize ("-O3")

#pragma optimize ("-O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int n;
int smallestFactor[1010101];
 
vector<int> primeFac(int x) {
  if (x == 1) return {1};
  vector<int> facs;
  while (x > 1) {
    int small = smallestFactor[x];
    if (facs.empty() || facs.back() != small) facs.push_back(small);
    x /= small;
  }
  return facs;
}
 
ll cnt[1010101]; // cnt of divisors seen so far
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n;
 
  for (int d = 2; d <= 1000000; d++) {
    if (smallestFactor[d] > 0) continue;
    for (int x = d; x <= 1000000; x += d) {
      if (smallestFactor[x] == 0) smallestFactor[x] = d;
      else smallestFactor[x] = min(smallestFactor[x], d);
    }
  }
 
  ll ans = 0;
 
  for (int i = 0; i < n; i++) {
    int x; cin>>x;
    
    if (x == 1) { ans += (ll)i; continue; }
 
    vector<int> facs = primeFac(x);
    int m = facs.size();
    int res = 0;
 
    for (int S = (1 << m) - 1; S >= 1; S--) {
      int div = 1;
      for (int j = 0; j < m; j++) {
        if (S & (1 << j)) {
          div *= facs[j];
        }
      }
 
      res += __builtin_popcount(S) % 2 ? +cnt[div] : -cnt[div];
 
      cnt[div]++;
    }
 
    ans += ll(i - res);
  }
 
  cout<<ans<<"\n";
}

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