Submission #847200

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX_N = 100030;    // Change as necessary
const ll  MODD = 1000000009; //

vector<ll> pr;
bool is_prime[MAX_N];

__int128 fast_exp_mod(__int128 b, __int128 n, __int128 m) {
  if (n == 0) return 1 % m;
  if (n % 2 == 0) return fast_exp_mod((b*b)%m, n/2, m);
  return (fast_exp_mod(b, n-1, m) * b) % m;
}

ll q_mod(ll x,ll m){ return (x >= m) ? x-m : x; }
ll mult_mod(ll x,ll y,ll m){ // Use int128
  __int128 X = x, Y = y, M = m;
  return ll(X * Y % M);
  ll r = 0;
  while(y){
    if(y % 2) r = q_mod(r+x,m);
    y >>= 1; x = q_mod(x << 1,m);
  } return r;
}

const ll val[] = {2,13,23,1662803};
bool isLargePrime(ll n){
  if(n < 100000) return false;
  for(auto p : pr){
    if(p*p*p > n) break;
    if(n % p == 0) return false;
  }
  
  ll s = __builtin_ctzll(n-1), d = (n-1) >> s;
  for(int i=0;i<4;i++){
    if(val[i] >= n) break;
    ll x = fast_exp_mod(val[i],d,n); // Use int128 in here
    if(x == 1 || x == n-1) continue;
    for(ll r=1;r<s;r++) if((x = mult_mod(x,x,n)) == n-1) goto nextPr;
    return false;
  nextPr:;
  }
  return true;
}

vector<pair<ll,int> > factor(long long x){
  vector<pair<ll,int> > ans;
  
  if(isLargePrime(x)){
    ans.emplace_back(x,1);
    return ans;
  }
  
  for(auto p : pr){
    if(p*p > x) break;
    if(x % p == 0){
      int ctr = 0;
      while(x % p == 0){
        x /= p;
        ctr++;
      }
      
      if(ctr % 3)
        ans.emplace_back(p,ctr%3);
    }
  }
  if(x != 1) ans.emplace_back(x,1);
  return ans;
}

ll A[MAX_N];
map<vector<pair<ll,int> >, int> M;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  pr.push_back(2);
  fill(is_prime,is_prime+MAX_N,true);
  for(int i=3;i*i<MAX_N;i++)
    if(is_prime[i])
      for(int j=i*i;j<MAX_N;j+=i)
        is_prime[j] = false;
  
  for(int i=3;i<MAX_N;i+=2)
    if(is_prime[i])
      pr.push_back(i);
  
  int n; cin >> n;
  for(int i=0;i<n;i++) cin >> A[i];
  
  for(int i=0;i<n;i++)
    M[factor(A[i])]++;
  
  int ans = 0;
  for(const auto& x : M){
    vector<pair<ll,int> > tmp = x.first;
    bool found = false;
    for(auto& p : tmp){
      p.second = (3-p.second)%3;
      found |= p.second;
    }
    
    if(!found) ans+=2;
    else if(M.count(tmp)){
      ans += max((ll)x.second,(ll)M[tmp]);
    } else {
      ans += x.second*2;
    }
  }
  
  cout << ans/2 << endl;
  
  return 0;
}

Submission Info

Judge Result