Submission #50681097

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    for (int j = 2; j * j <= a[i]; j++) {
      while (a[i] % (j * j) == 0) a[i] /= j * j;
    }
  }
  map<int, int> cnt;
  int n0 = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == 0) {
      n0++;
    } else {
      cnt[a[i]]++;
    }
  }
  int64 ans = 0;
  ans += (int64)n0 * (n0 - 1) / 2;
  ans += (int64)n0 * (n - n0);
  for (auto [k, v] : cnt) {
    ans += (int64)v * (v - 1) / 2;
  }
  cout << ans << '\n';

  return 0;
}

Submission Info

Judge Result