Submission #1315934

---

Source Code Expand

#include<bits/stdc++.h>
#include<map>
#define LL long long
#define LD long double
#define INF (1LL<<60)
using namespace std;
map<LL,LL> :: iterator it;
map<LL,LL> F,G;
int n,ans; LL a[100005],p[64],lp;
LL fpc(LL x,LL y,LL mo){ return ((x*y-(LL)((LD)x*y/mo)*mo)%mo+mo)%mo;}
LL fpm(LL x,LL y,LL mo){ LL s=1; while(y){ if(y&1) s=fpc(s,x,mo); y>>=1,x=fpc(x,x,mo);} return s;}
LL gcd(LL x,LL y){ return x ? gcd(y%x,x) : y;}
bool miller_rabin(LL p)
{
	LL a=rand()%(p-1)+1,q=p-1,x,y;
	if(p<=3) return 1;
	while(!a) a=rand()%p;
	for(;(q&1)^1;q>>=1);
	x=fpm(a,q,p);
	for(;q<p-1;q<<=1,x=y){
		y=fpc(x,x,p);
		if(y==1&&x!=1&&x!=p-1) return 0;
	  }
	return x==1;
}
bool test(LL x)
{
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	if(!miller_rabin(x)) return 0;
	return 1;
}
LL pollard_rho(LL n)
{
	LL d,c,x,y,a,b;
	for(c=2;;c++){
		y=1,b=a=rand()%n;
		for(x=1;x;x++){
			a=(fpc(a,a,n)+c)%n;
			if(b==a) break;
			d=gcd(abs(b-a),n);
			if(d!=1) return d;
			if(x==y) y<<=1,b=a;
		  }
	  }
	return 0;
}
void divide(LL x)
{
	LL d;
	if(x==1) return ;
	if(x==2){ p[++lp]=2; return ;}
	if(x==4){ p[++lp]=2,p[++lp]=2; return ;}
	if(test(x)){ p[++lp]=x; return ;}
	d=pollard_rho(x);
	divide(d);
	divide(x/d);
}
int main()
{
	int i,k,l,tag=0; LL y,z;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(i=1;i<=n;i++){
		lp=0,divide(a[i]);
		sort(p+1,p+lp+1);
		y=z=1;
		for(k=1;k<=lp;k=l){
			for(l=k;l<=lp&&p[k]==p[l];l++);
			if((l-k)%3==2) y*=p[k]*p[k],z*=p[k];
			if((l-k)%3==1){
				y*=p[k];
				if(z>0&&z<=INF/p[k]/p[k]) z*=p[k]*p[k];
				else z=-1;
			  }
		  }
		if(z==-1){ ans++; continue;}
		if(y==1){
			if(!tag) ans++,tag=1;
			continue;
		  }
		F[y]++,G[y]=z;
	  }
	for(it=F.begin();it!=F.end();it++){
		y=G[it->first],z=F[y];
		if(it->second>z||(it->second==z&&it->first>y))
			ans+=it->second;
	  }
	cout<<ans;
	return 0;
}

Submission Info

Compile Error

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

Judge Result