[数论记录]AT2004 [AGC003D] Anticube
command_block
2021-01-12 10:33:52
**题意** : 给定一个长度为 $n$ 的整数集合 $S$ ，选取一个最大的 $T\subseteq S$ ，使得 $T$ 中没有两个数的乘积是完全立方数。
$n\leq 10^5,S\subseteq[1,10^{10}]$ ，时限$\texttt{5s}$。
------------
一个显然的做法是，将每个数质因数分解，然后次数模 $3$ 归类。
这样，一个类和恰好另一个类对应乘积是完全立方数。
特殊地，完全立方数本身对应自己，所以至多选一个完全立方数。
否则，在一对配对的类中，选出大小较大的。
但是，在这个数据范围下没有使用的质因数分解方法，考虑分析性质。
将所有完全立方数特殊处理。
先把 $\leq s^{1/3}$ 的质数都暴力除掉，这部分复杂度为 $O(ns^{1/3}/\log s)$。
此时，余下的部分可能形如 $p,p^2,p_1p_2$ 。
对于 $p^2$ 的情况，需要补乘 $p^{3k+1}$ 才能变成立方，显然只有可能是 $p$。
对于其他情况，如余下 $m$，需要补乘 $m^{3k+2}$ 才能变成立方，显然还只有可能是 $m^2$。
注意 $m^2$ 可能超出 $s$，甚至爆 `long long`。
于是，我们按照 （$s^{1/3}$以内质因子模 $3$，剩余质因子配对） 来分类即可。
```cpp
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define ll long long
#define mp make_pair
#define Pr pair<ll,ll>
#define MaxS 2250
using namespace std;
const int lim=2200;
const ll INF=10000000000ll;
int p[MaxS/4],tn;
bool e[MaxS];
void sieve()
{
for (int i=2;i<=lim;i++){
if (!e[i])p[++tn]=i;
for (int j=1;j<=tn&&i*p[j]<=lim;j++){
e[i*p[j]]=1;
if (i%p[j]==0)break;
}
}
}
int n,ans=1,flag;
map<Pr,int> sav;
void calc(ll x)
{
ll t=pow(x,1.0/3);
t=max(1ll,t-3);while(t*t*t<x)t++;
if (t*t*t==x){flag=1;return ;}
ll t1=1;
for (int i=1;i<=tn;i++){
int c=0;
while(x%p[i]==0){c++;x/=p[i];}
c%=3;
for (int t=1;t<=c;t++)t1*=p[i];
}sav[mp(t1,x)]++;
}
Pr mir(Pr a)
{
ll t1=1,x=a.first,y=a.second,t=sqrtl(y);
if (t*t!=y){
if (y>1000000000)return mp(0,0);
t=y*y;
}
for (int i=1;i<=tn;i++){
int c=0;
while(x%p[i]==0){c++;x/=p[i];}
c=(6-c)%3;
for (int t=1;t<=c;t++){
t1*=p[i];
if (t1>=INF)return mp(0,0);
}
}return mp(t1,t);
}
int main()
{
scanf("%d",&n);
sieve();
for (int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
calc(x);
}
map<Pr,int>::iterator it=sav.begin();
for (;it!=sav.end();it++){
Pr buf=mir(it->first);
if (!sav.count(buf))
ans+=it->second*2;
else ans+=max(it->second,sav[buf]);
}printf("%d",ans/2+flag);
return 0;
}
```