2020牛客NOIP赛前集训营-普及组（第一场） C- 牛牛的最大兴趣组

牛牛的最大兴趣组

• 前言

  既然没人写那我就来吧。

• 分析

  小菜鸡似乎过了很久才分析出来。
  可以确定，一个数能被唯一分解
  
  然后题目要求两个数相乘开三次方不能开出整数
  
  如果a有一个因子i使得a=i * i * i，那么我们可以毫不犹豫的把它拿出来
  
  这样的话，能不能得出整数其实就是后面这部分的事情了。所以第一步，我们先处理掉一个数的所有满足条件的因子(这个因子的三次方也能被原数整除)。同时记录一下剩下的数的大小
  
  还是
  
  如果我们想让后面的根号与某一个数相乘能得到一个整数，那么另一个数应该满足什么条件?如果要开出三次方，明显，它的唯一分解的每一个质数的幂次都得是三的倍数。假设
  
  那么另一个数一定等于
  
  所以如果想要得到最大的参与数，其实只需要记录一下这两个数哪一个的贡献更大，加上就行。但是别忘了考虑1。即这个数开三次方本就是一个整数的时候，这个时候只能算作一个贡献。

• 代码

#include<bits/stdc++.h>

#define dl double
#define ll long long

using namespace std;

const int N=1e5+10;

ll n,ans,tot;
ll a[N],to[N],b[N],pr[N],kp[N];
bool bb[N];

map<ll,int>sum;
map<ll,bool>vis;

inline void Pre()
{
    for (ll i=2;i<N;i++)
    {
        if(!bb[i]) pr[++tot]=i;
        for (ll j=1;j<=tot&&i*pr[j]<N;j++)
        {
            bb[i*pr[j]]=1;
            if(i%pr[j]==0) break;
        }
    }
    for (int i=1;i<=tot;i++) kp[i]=pr[i]*pr[i]*pr[i];
}

inline void get(ll id,ll x)
{
    ll k=x;
    for (ll i=1;i<=tot;i++)
    {
        if(kp[i]>k) break;
        while(k%kp[i]==0) k/=kp[i];
    }//开三次方 

    //分解质因数
    ll now=1;b[id]=k;++sum[k];
    for (ll i=1;i<=tot;i++)
    {
        if(pr[i]>k) break;
        int cnt=0;
        while(k%pr[i]==0) ++cnt,k/=pr[i];
        if(cnt==1) now=now*pr[i]*pr[i];
        else if(cnt==2) now*=pr[i];
    }
    if(k>1) now*=k*k;
    to[id]=now;
}

int main()
{
    scanf("%lld",&n);Pre();
    for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (ll i=1;i<=n;i++) get(i,a[i]);

    for (ll i=1;i<=n;i++)
    {
        if(vis[b[i]]) continue;
        if(b[i]==1) ans+=1;
        else ans+=max(sum[b[i]],sum[to[i]]);
        vis[b[i]]=1;vis[to[i]]=1;
    }

    printf("%lld\n",ans);

    return 0;
}