题解：AT_agc003_d [AGC003D] Anticube

· · 题解

前置知识：埃氏筛法（或线性筛法）、质因数分解。

再次感谢 @Tenshi 的题解，提供了重要思路。

本题解在更加详细的同时，增加了一些结论证明，简化了找质因数的过程，不需要再使用 Pollard-Rho 这种高级算法。通过这种方法，这道题的难度可以降低到蓝或更低。

题目要求“任意两个数的积都不是完全立方数”，即数与数之间存在互斥关系。又要求“选出最多的数”，很容易想到最大独立集。考虑如何快速判断两个数是否互斥：

将一个数质因数分解后，是否是立方数只与其是否所有质因子的指数都是 3 的倍数有关，所以可以将所有的指数都模 3，不影响结果。

如此操作以后，一个数可以在所有质因子指数都模 3 以后简化，使所有质因子的指数都属于 \{0,1,2\}，而两个数是否互斥（乘积是否为立方数）也很好判断了。将 x 的简化形式 x' 质因数分解为 \prod p_i^{c_i}，某个数 y 与 x 的乘积为立方数当且仅当其简化形式 y'=\prod p_i^{(3-c_i) \bmod 3}（注意需要再次取模）。

这样，某个数的简化形式的互斥对象就有了唯一确定的简化形式，并且这是一一对应的，x' 与 y' 互斥时，y' 也与 x' 互斥，例如 2 和 4。

根据这个计算方式建图，以所有的简化形式为结点，所有的互斥关系为边，所求即为这张图上的最大独立集。

这样建图出来以后可以发现，所有的完全立方数简化形式都为 1，互斥对象也都为 1。即：所有的完全立方数都两两互斥，只能选一个，且完全立方数不与其它任何点连边，是孤立的。

此外，非完全立方数的互斥对象都一定不是自己，证明：对非完全立方数进行简化，其至少有一个质因子的指数不为 0（否则就是完全立方数了），只可能是 1 或 2，对应的互斥指数分别为 2 和 1，都不可能与自己相同。所以非完全立方数的互斥对象至少有一个质因子的指数与自己不同。根据唯一分解定理，这两个数也一定不同。

综上所述，除去完全立方数是可能有自环的孤点，其它非完全立方数点总是两两一对连边，且不会形成自环，在这样的图上找最大独立集就简单多了，两侧的点只能选一边，当然是选大的那一侧了。

具体来说，设简化形式 x' 出现了 p 次，其互斥对象 y' 出现了 q 次，那么这一对点的最大独立集就是 \max\{p,q\}。

接下来考虑如何求取某个数的简化形式和其互斥对象的简化形式：

简化某个数需要将其质因数分解，暴力当然是不行的，我们需要一些优化。

记 V = \sqrt{\max s}，极限时间复杂度为 O(V \log\log V + \frac{V}{\ln V} N)（埃筛）或 O(V + \frac{V}{\ln V} N)（线筛），随机数据下对单个数分解质因数平均循环次数不到 1000，可过此题。

AC 记录：洛谷，AtCoder。

代码：

#include<cstdio>
#include<bitset>
#include<vector>
#include<unordered_map>
#define LL long long
using namespace std;

const int N=1e5+5,SA=1e5;
int n;
LL a[N];

bitset<SA+5> is_prime;
int prime[N],prime_idx;
void Erato()
{
    for(int i=2;i<=SA;i++)
        is_prime[i]=true;
    for(int i=2;i<=SA;i++)
        if(is_prime[i])
        {
            prime[++prime_idx]=i;
            for(LL j=1ll*i*i;j<=SA;j+=i)
                is_prime[j]=false;
        }
    return;
}

unordered_map<LL,int> ump;
unordered_map<LL,LL> rev;
void connect(int id)
{
    LL x=a[id];
    auto spow = [&](LL x,int y) -> LL //计算x的y次方（y≤3）
    {
        switch(y)
        {
            case 0: return 1;
            case 1: return x;
            case 2: return x*x;
            case 3: return 1;
            default: return -1;
        }
    };
    LL simp=1,cur=1;
    for(int i=1;i<=prime_idx&&prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0)
        {
            int cnt=0;
            while(x%prime[i]==0)
            {
                x/=prime[i];
                cnt++;
            }
            cnt%=3;
            simp*=spow(prime[i],cnt);
            cur*=spow(prime[i],3-cnt);
        }
    if(x>1)
    {
        simp*=spow(x,1);
        cur*=spow(x,2);
    }
    ump[simp]++;
    rev[simp]=cur;
    rev[cur]=simp;
    ump[cur];
    return;
}

unordered_map<LL,bool> is_cub;
unordered_map<LL,bool> vst;
int main()
{
    Erato();
    for(int i=1;i<=2200;i++)
        is_cub[1ll*i*i*i]=true;
    scanf("%d",&n);
    bool have_cube=false;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(is_cub[a[i]]) have_cube=true;
        else connect(i);
    }
    int ans=0;
    for(pair<LL,int> p: ump)
    {
        if(vst[p.first]) continue;
        ans+=max(p.second,ump[rev[p.first]]);
        vst[rev[p.first]]=true;
    }
    printf("%d\n",ans+have_cube);
    return 0;
}