牛牛最大的兴趣组

题解：

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define int long long  //由于可能超出int，所以设置为long long类型，为了方便，可以直接将int 定义为long long，但是注意由于后面的int main，只能返回int类型，不能返回longlong，所以可以写成signed main
int n,x,a[N],u,b[N],ans=0;//a[t]：记录第t个数剔除k^3后的数，b[t]：与第t个数剔除后的数相乘会得到一个整数的三次方的数，即与a[t]互斥的数，ans:最大兴趣组
map<int,int>num;//记录剔除k^3后得到的每个数的出现的次数
map<int,bool>pd;//判断pd[i]这种情况有没有讨论过

void solved(int x,int t){
	for(int i=2;i*i*i<=x;i++){  //1.由于任何一个整数n=a*k^3表示，k是最大的立方因子，所以当a=1时，得到的最大的k是<=x的开三次根号，由于遍历因子1没有意义，不会改变x,所以从2开始，最大为x的开三次根号
		int l=i*i*i;
		while(x%l==0){//将x中剔除最大的立方因子k^3
			x/=l;
		}
	}
	a[t]=x;num[x]++;u=1;//可以得到第t个数剔除后的结果存在a[t]中，记录这个剔除后的数出现的次数，num[x]++
    
    //接下来找与a[t]相乘会排斥的数，记在b[t]中
    //因为之前x已经剔除了k^3，所以最多只能剔除k^2，所以是i*i<=x
	for(int i=2;i*i<=x;i++){
        //如果x可以被i^2整除，则说明x只需要再乘以一个i，就会出现i^3，所以u要乘以一个i,b[t]=u=i;a[t]=x,表示a[t]*b[t]=i^3会互斥
		if(x%(i*i)==0){
			x/=(i*i);
			u*=i;
		}
        //同理，如果x可以被i整除，则说明x只需要再乘以i*i，就会出现i^3，即u=i*i,b[t]=u;a[t]=i;表示a[t]*b[t]=i^3会互斥
		if(x%i==0){
			x/=i;
			u*=i*i;
		}
	}
    //如果最后得到的x还是大于1，表示是质数，没有除1和本身外的因子了，所以这个数x，当遇到x*x的时候会得到x^3，所以b[t]=x^2
	if(x>1){
		u*=x*x;
	}
	b[t]=u;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		solved(x,i);//第i个数x
	}
    //遍历剔除k^3后的n个数
	for(int i=1;i<=n;i++){
        //如果该种情况还没有考虑过，那么就考虑
		if(!pd[a[i]]){
            //如果剔除后得到的数是1，那么由于其本身就是k^3的形式，所以加入兴趣组后对其他的没有影响，所以可以加入ans++
			if(a[i]==1){
				ans++;
			}else{
                //否则就从两个互斥的a[t]与b[t]中选择出现次数最多的一个，贪心的思想，这样才能得到的最大兴趣组
				ans+=max(num[a[i]],num[b[i]]);
			}
            //标记这两种情况出现过
			pd[a[i]]=1;pd[b[i]]=1;
		}
	}
	cout<<ans;
	return 0;
}