AGC 003 D

AGC003D.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

vector<ll> primes;
void make_primes(){
    primes.pb(2);
    for(ll n = 3; n <= 2200; n++){ // 2200^3 > 10^10
        bool isPrime = true;
        for(ll i = 0; primes[i] * primes[i] <= n && i < primes.size(); i++){
            if(n % primes[i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) primes.pb(n);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    make_primes();
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) {
        cin >> A[i];
        for(ll prime: primes){
            while(1){
                if(A[i] % (prime * prime * prime) == 0){
                    A[i] /= prime * prime * prime;
                }
                else{
                    break;
                }
            }
        }
    }
    sort(all(A));
    vector<pair<ll, int>> C;
    map<ll, int> M;
    ll num = -1;
    rep(i, N){
        if (num == A[i]){
            C.back().second++;
        }
        else{
            C.pb(mp(A[i], 1));
            M[A[i]] = (int)C.size(); // index + 1
        }
        num = A[i];
    }
    
    vector<int> vis(C.size(), 0); // チェックしたか
    int ret = 0;
    
    // a*b^2 and a^2*b
    rep(i, C.size()){
        if(vis[i] > 0 || C[i].first == 1) continue;
        ll a = C[i].first;
        ll b = 1;
        for(ll prime: primes){
            if(a % (prime * prime) == 0){
                a /= (prime * prime);
                b *= prime;
            }
        }
        if(M[a * a * b] > 0){
            ret += max(C[i].second, C[M[a * a * b] - 1].second);
            vis[i] = 1, vis[M[a * a * b] - 1] = 1;
        }
        else{
            ret += C[i].second;
            vis[i] = 1;
        }
    }
    
    // a and a^2
    rep(i, C.size()){
        if(C[i].first > 100000) break; // (10^5)^2=10^10
        if(vis[i] > 0 || C[i].first == 1) continue;
        ll a = C[i].first;
        ll b = a * a;
        if(M[b] > 0){
            ret += max(C[i].second, C[M[b] - 1].second);
            vis[i] = 1, vis[M[b] - 1] = 1;
        }
        else{
            ret += C[i].second;
            vis[i] = 1;
        }
    }
    
    // 1だけ特別に処理
    rep(i, C.size()){
        if(vis[i] == 0){
            if(C[i].first == 1) ret++;
            else ret += C[i].second;
        }
    }
    
    output(ret, 0);
    return 0;
}