https://www.zybuluo.com/ysner/note/1304774
题面
给定(n)个数(s_i),要求从中选出最多的数,满足任意两个数之积都不是完全立方数。
- (nleq10^5,s_ileq10^{10})
解析
很显然的是，完全平方数的所有质因子指数都是(3)的倍数。
考虑质因数分解。
我们可以把每个数质因数分解，所有大于(3)的指数模(3)不影响答案。
然后维护一下该数在处理后的值(A)，和对应的能与其凑成完全平方数的值(B)。
(A)与(B)不能共存。
于是我们存一下(A)的出现次数，最后对于每个数贪心取(A)和(B)中出现次数更多的那个即可。
注意取过的数不要再取，(A=B)时只能取一个。
好了问题来了，质因数分解的复杂度不太对。
有一个显而易见的结论，(x)中大于(x^{frac{1}{3}})的因子至多只有(2)个。
于是复杂度就对了？不虚，时限(5s)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=1e5+100;
ll n,a[N],pri[N],tot,l[N],r[N],ans;
map<ll,int>num,use;
bool vis[N];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void Pre(re int n)
{
vis[1]=1;
fp(i,2,n)
{
if(!vis[i]) pri[++tot]=i;
for(re int j=1;j<=tot&&i*pri[j]<=n;++j)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
il void split(re ll x,re int p)
{
re ll A=1,B=1;
fp(i,1,tot)
{
re int gu=0;
while(x%pri[i]==0)
{
x/=pri[i];++gu;
}
gu%=3;
if(gu==1) B=B*pri[i]*pri[i];
if(gu==2) A=A*pri[i]*pri[i],B=B*pri[i];
if(x<pri[i]) break;
}
if(x>1)
{
re ll t=sqrt(x);
if(t*t==x) A=A*x,B=B*t;
else A=A*x,B=B*x*x;
}
l[p]=A;r[p]=B;
++num[A];
}
int main()
{
Pre(4000);
n=gi();
fp(i,1,n) a[i]=gi(),split(a[i],i);
fp(i,1,n)
if(!use[l[i]])
{
use[l[i]]=use[r[i]]=1;
if(l[i]==r[i]) ++ans;
else ans+=max(num[l[i]],num[r[i]]);
}
printf("%lld
",ans);
return 0;
}