AT2004 Anticube

https://www.zybuluo.com/ysner/note/1304774

题面

给定\(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;

}

巴特西

AT2004 Anticube

https://www.zybuluo.com/ysner/note/1304774

题面

解析

最新文章

热门文章