Submission #847652

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 100100;

bool u[M];
int m = 0, p[M];
ll sq[M], cb[M];

void sito() {
  for (int i = 2; i < M; ++i)
    if (!u[i]) {
      p[m++] = i;
      for (int j = i; j < M; j += i)
        u[j] = true;
    }

  copy(p, p + m, sq);
  copy(p, p + m, cb);

  for (int i = 0; i < M; ++i) {
    sq[i] *= p[i];
    cb[i] *= sq[i];
  }
  
  //cerr << "m = " << m << endl;
}

int n;
ll a[M];
map<pair<ll, ll>, int> cnt;

void read() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> a[i];
}


void kill() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; cb[j] <= a[i]; ++j)
      while (a[i] % cb[j] == 0) {
        a[i] /= cb[j];
      }

  bool is_cube = false;
  int sum = 0;

  for (int i = 0; i < n; ++i) {
    ll A = a[i];

    if (A == 1) {
      is_cube = true;
      continue;
    }

    ll B = 1;
    for (int j = 0; sq[j] <= A; ++j)
      if (A % sq[j] == 0) {
        A /= sq[j];
        B *= p[j];
      }

    //cerr << A << " " << B << endl;

    int val = 1;
    if (A > B) {
      swap(A, B);
      val = -1;
    }

    cnt[make_pair(A, B)] += val;
    sum++;
  }

  int ans = 0;
  ans += sum;
  for (auto x : cnt)
    ans += abs(x.second);

  ans /= 2;
  
  if (is_cube)
    ++ans;

  cout << ans << endl;
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  sito();
  read();
  kill();
}

Submission Info

Judge Result