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> primes;

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;
}

int cnt[1010101]; // cnt of divisors seen so far
int occ[20];

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 += i;
      continue;
    }
    vector<int> facs = primeFac(x);
    int m = facs.size();
    for (int j = 0; j < m; j++) occ[j] = 0;
    int res = 0;

    for (int S = (1 << m) - 1; S >= 1; S--) {
      int div = 1;
      int rem = 1e9;

      for (int j = 0; j < m; j++) {
        if (S & (1 << j)) {
          div *= facs[j];
          rem = min(rem, occ[j]);
        }
      }

      int beforeCnt = cnt[div];
      beforeCnt -= rem;
      //cout<<"pos "<<i<<" with div of "<<div<<" has beforecnt = "<<beforeCnt<<"\n";
      //cout<<"rem is "<<rem<<"\n";
      for (int j = 0; j < m; j++) {
        if (S & (1 << j)) occ[j] += beforeCnt;
      }

      res += beforeCnt;
      cnt[div]++;
    }

    /*
    cout<<"at pos "<<i<<" cnt to left is "<<res<<"\n";
    cout<<"occ: ";
    for (int j = 0; j < m; j++) {
      cout<<occ[j]<<" ";
    }
    cout<<"\n";
    */
    ans += ll(i - res);
  }

  cout<<ans<<"\n";
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 2, 3

Verdict: WRONG ANSWER

Test 4

Group: 3

Verdict: WRONG ANSWER

Test 5

Group: 3

Verdict: WRONG ANSWER

Test 6

Group: 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED