AT2004 Anticube

数论 贪心

题面

给定$n$个数$s_i$,要求从中选出最多的数,满足任意两个数之积都不是完全立方数。

• $n\leq10^5,s_i\leq10^{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\n",ans);
  return 0;
}