Submission #1837849

---

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=100010;

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

inline void Pre(){
  for(int i=2;i<=100000;i++){
    if(!p[i]) p[++*p]=i;
    for(int j=1;j<=*p && 1LL*p[j]*i<=100000;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(b[i]>10000000000LL) return ans++,void();
	}
    }
  if(sqrt[a[i]]){
    c[i]*=sqrt[a[i]];
    b[i]*=a[i]; if(b[i]>10000000000LL) return ans++,void();
  }
  else{
    c[i]*=a[i];
    b[i]*=a[i]; if(b[i]>10000000000LL) return ans++,void();
    b[i]*=a[i]; if(b[i]>10000000000LL) return ans++,void();
  }
  if(c[i]==1){
    if(!ct[1]) ans++; ct[1]=1; return ;
  }
  ct[c[i]]++;
  v.pb(abcd(c[i],b[i]));
}

int main(){
  read(n); Pre();
  for(int i=1;i<=n;i++) {
    read(a[i]),work(i);
  }
  vis[1]=1;
  for(int i=0;i<v.size();i++){
    if(vis[v[i].fi]) continue;
    vis[v[i].fi]=vis[v[i].se]=1;
    ans+=max(ct[v[i].fi],ct[v[i].se]);
  }
  printf("%d\n",ans);
  return 0;
}

Submission Info

Judge Result