Submission #847121

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
  bool E[100001]={0};
  vector<int> P;
  for(int i=2;(long long)i*i*i<=10000000000ll;i++){
    if(!E[i]){
      for(int j=2*i;(long long)j*j*j<=10000000000ll;j+=i){
	E[j]=1;
      }
      P.push_back(i);
    }
  }
  int NP=P.size();
  int n;
  scanf("%d",&n);
  static long long S[100000];
  for(int i=0;i<n;i++){
    scanf("%lld",S+i);
  }
  static long long s[100000];
  for(int i=0;i<n;i++){
    s[i]=1ll;
    for(int j=0;j<NP&&(long long)P[j]*P[j]*P[j]<=S[i];j++){
      int c=0;
      while(S[i]%P[j]==0){
	S[i]/=P[j];
	c++;
      }
      if(c%3==1){
	s[i]*=P[j];
      }
      else if(c%3==2){
	s[i]*=P[j]*P[j];
      }
    }
    s[i]*=S[i];
  }
  sort(s,s+n);
  vector<pair<long long,int> > V;
  for(int i=0;i<n;i++){
    if(i==0||s[i-1]<s[i]){
      V.push_back(make_pair(s[i],1));
    }
    else{
      V[V.size()-1].second++;
    }
  }
  int a=0;
  for(int i=0;i<V.size();i++){
    long long A=V[i].first,B=1ll;
    if(A==1){
      a++;
      continue;
    }
    for(int j=0;j<NP&&(long long)P[j]*P[j]*P[j]<=A;j++){
      int c=0;
      while(A%P[j]==0){
	A/=P[j];
	c++;
      }
      if(c%3==1){
	if(0<=B&&B<=10000000000ll){
	  B*=P[j]*P[j];
	}
	else{
	  B=-1;
	}
      }
      else if(c%3==2){
	if(0<=B&&B<=10000000000ll){
	  B*=P[j];
	}
	else{
	  B=-1;
	}
      }
    }
    long long t=(long long)(sqrt((double)A)+0.5);
    if(t*t==A){
      if(0<=B&&B<=10000000000ll){
	B*=t;
      }
      else{
	B=-1;
      }
    }
    else{
      if(0<=B&&A<=1000000ll){
	B*=A*A;
      }
      else{
	B=-1;
      }
    }
    //printf("%lld %lld %lld\n",V[i].first,V[i].second,B);
    int j=lower_bound(V.begin(),V.end(),make_pair(B,0))-V.begin();
    if(j==V.size()||V[j].first>B){
      a+=V[i].second;
    }
    else if(V[i].first<V[j].first){
      a+=max(V[i].second,V[j].second);
    }
  }
  printf("%d\n",a);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:21:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:24:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",S+i);
                      ^

Judge Result