Submission #1315946
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;
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;
srand(2222303);
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=z>0 ? z*p[k] : -1;
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:65:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:67:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&a[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1400 |
Status |
|
AC |
× 1 |
WA |
× 6 |
TLE |
× 26 |
RE |
× 5 |
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
TLE |
2103 ms |
1024 KB |
02.txt |
TLE |
2103 ms |
1024 KB |
03.txt |
TLE |
2103 ms |
1024 KB |
04.txt |
TLE |
2103 ms |
1024 KB |
05.txt |
TLE |
2103 ms |
1024 KB |
06.txt |
TLE |
2103 ms |
1024 KB |
07.txt |
TLE |
2103 ms |
1024 KB |
08.txt |
TLE |
2103 ms |
1024 KB |
09.txt |
TLE |
2103 ms |
1024 KB |
10.txt |
TLE |
2103 ms |
1024 KB |
11.txt |
TLE |
2103 ms |
1024 KB |
12.txt |
TLE |
2103 ms |
1024 KB |
13.txt |
TLE |
2103 ms |
1024 KB |
14.txt |
TLE |
2103 ms |
1024 KB |
15.txt |
TLE |
2103 ms |
1024 KB |
16.txt |
TLE |
2103 ms |
1024 KB |
17.txt |
TLE |
2103 ms |
1024 KB |
18.txt |
TLE |
2103 ms |
1024 KB |
19.txt |
TLE |
2103 ms |
1024 KB |
20.txt |
TLE |
2103 ms |
1024 KB |
21.txt |
TLE |
2103 ms |
1024 KB |
22.txt |
TLE |
2103 ms |
1792 KB |
23.txt |
TLE |
2103 ms |
3840 KB |
24.txt |
TLE |
2104 ms |
4992 KB |
25.txt |
TLE |
2104 ms |
4992 KB |
26.txt |
TLE |
2104 ms |
6528 KB |
27.txt |
RE |
907 ms |
11392 KB |
28.txt |
WA |
1031 ms |
1024 KB |
29.txt |
WA |
1036 ms |
1024 KB |
30.txt |
RE |
789 ms |
1024 KB |
31.txt |
AC |
1 ms |
256 KB |
32.txt |
RE |
133 ms |
256 KB |
33.txt |
WA |
1 ms |
256 KB |
34.txt |
RE |
135 ms |
256 KB |
35.txt |
WA |
1 ms |
256 KB |
36.txt |
WA |
1 ms |
256 KB |
s1.txt |
RE |
99 ms |
256 KB |
s2.txt |
WA |
1 ms |
256 KB |