Submission #1837860

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <ctime>
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<ll,ll> abcd;

const int N=1000010;

int n,p[N];
ll a[N],b[N],c[N];
map<ll,int> vis,ct,Sqrt;
map<ll,ll> op;

inline void Pre(){
  for(int i=2;i<=1000000;i++){
    if(!p[i]) p[++*p]=i;
    for(int j=1;j<=*p && 1LL*p[j]*i<=1000000;j++){
      p[p[j]*i]=1; if(i%p[j]==0) break;
    }
  }
  for(int i=1;i<=*p;i++) Sqrt[1LL*p[i]*p[i]]=p[i];
}

vector<abcd> v;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void read(ll &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline void read(int &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

int ans;

inline void work(int i){
  b[i]=1; c[i]=1;
  for(int j=1;j<=*p && 1LL*p[j]*p[j]<=a[i] && p[j]<=2200;j++)
    if(a[i]%p[j]==0){
      int cnt=0; while(a[i]%p[j]==0) a[i]/=p[j],cnt++;
      cnt%=3; for(int k=1;k<=cnt;k++) c[i]*=p[j];
      if(cnt) for(int k=cnt+1;k<=3;k++) b[i]*=p[j];
    }
  if(Sqrt[a[i]])
    c[i]*=Sqrt[a[i]],b[i]*=a[i];
  else
    c[i]*=a[i],b[i]*=a[i]*a[i];
  ct[c[i]]++;
  if(c[i]>b[i]) swap(b[i],c[i]);
  op[c[i]]=b[i];
}

int main(){
  read(n); Pre();
  for(int i=1;i<=n;i++) {
    read(a[i]),work(i);
  }
  for(auto c : op){
    if(c.fi==c.se) ans++;
    else ans+=max(ct[c.fi],ct[c.se]);
  }
  printf("%d\n",ans);
  return 0;
}

Submission Info

Judge Result