WA 了一个点。

#include<bits/stdc++.h>
#define int long long
#define inf 2147483647
using namespace std ;
int n , a[112345] , now[112345] , head[112345] , cnt=0 , sum[112345] , need[112345] , s , t , dep[112345] , tot=0 , before[112345] , temp[112345]  ;
bool f[112345] ;
unordered_map<int,int> mp , number ;
struct node{
	int to , next , w ;
}e[5123456];
void use(int u,int v,int w){
	e[cnt].to = v ;
	e[cnt].w = w ;
	e[cnt].next = head[u] ;
	head[u] = cnt++ ;
}
void newnet(int u,int v,int w){
	use(u,v,w) ;
	use(v,u,0) ;
}
bool bfs(){
	for(int i=1;i<=t;i++) f[i]=0 , dep[i]=inf , now[i]=head[i] ;
	queue<int> q ;
	q.push(s) ;
	dep[s] = 0 ;
	while(!q.empty()){
		int u=q.front() ;
		q.pop() ;
		f[u]=0 ;
		for(int i=head[u];~i;i=e[i].next){
			int x=e[i].to ;
			if(dep[u]+1<dep[x]&&e[i].w){
				dep[x] = dep[u]+1 ;
				if(!f[x]){
					f[x]=1 ;
					q.push(x) ;
				}
			}
		}
	}
	return dep[t]!=inf ;
}
int dfs(int u,int sum){
	if(u==t) return sum ;
	int use=0 ;
	for(int i=now[u];~i;i=e[i].next){
		now[u] = i ;
		int x=e[i].to ;
		if(dep[u]+1!=dep[x]||!e[i].w) continue ;
		int temp=dfs(x,min(sum,e[i].w)) ;
		if(!temp) continue ;
		e[i].w -= temp ;
		e[i^1].w += temp ; 
		sum -= temp ;
		use += temp ;
		if(!sum) break ;
	}
	return use ;
}
int dinic(){
	int ans=0 ;
	while(bfs()) ans += dfs(s,inf) ; 
	return ans ;
}
vector<int> Te[112345] ;
void stain(int u,bool color){
	f[u]=1 ;
	if(color) newnet(u,t,mp[before[u]]) ;
	else newnet(s,u,mp[before[u]]) ;
	for(auto x:Te[u]){
		if(f[x]) continue ;
		if(!color) newnet(u,x,inf) ;
		stain(x,!color) ;
	}
}
int ksm(int x,int k,int M){
	__int128 ans=1 , temp=x , mod=M ;
	while(k){
		if(k&1) ans *= temp , ans %= mod ;
		temp *= temp ;
		temp %= mod ;
		k >>=1 ;
	}
	return (long long)ans ;
}
set<pair<int,int>> st ;
signed main(){
	memset(head,-1,sizeof head) ;
	cin >> n ;
	for(int i=1;i<=n;i++) scanf("%lld",a+i) , now[i] = a[i] , sum[i]=1 , need[i]=1 ;
	for(int i=1;i<=n;i++){
		int temp=cbrt(a[i]) , temp1=a[i] ;
		for(int j=2;j<=temp;j++){
			if(now[i]%j) continue ;
			int num=j*j*j ;
			while(now[i]%num==0&&now[i]) now[i] /= num , temp1 /= num ;
			if(temp1%(j*j)==0) sum[i] *= j*j , temp1 = temp1/j/j , need[i] *= j ;
			else if(temp1%j==0) sum[i] *= j , need[i] *= j*j , temp1 /= j ;
		}
		mp[now[i]]++ ;
		sum[i] = now[i]/sum[i] ;
		if(sum[i]!=1&&(sum[i]==2||ksm(sum[i]-1,sum[i]-1,sum[i])==1)){
			need[i] *= sum[i]*sum[i] ;
		}else if(((long long)sqrt(sum[i]))*((long long)sqrt(sum[i]))==sum[i]){
			need[i] *= sqrt(sum[i]) ;
		}
	}
	unordered_map<int,int>::iterator it=mp.begin() ;
	for(it=mp.begin();it!=mp.end();it++)tot++ , number[it->first] = tot , before[tot] = it->first ;
	s = tot+1 , t = tot+2 ;
	for(int i=1;i<=n;i++) if(mp[need[i]]&&!st.count(make_pair(number[need[i]],number[now[i]]))&&need[i]!=now[i]) Te[number[need[i]]].push_back(number[now[i]]) , Te[number[now[i]]].push_back(number[need[i]]) , st.insert(make_pair(number[need[i]],number[now[i]])) , st.insert(make_pair(number[now[i]],number[need[i]])) ;
	for(int i=1;i<=tot;i++)	if(!f[i]) stain(i,0) ;
	if(mp[1]>0) mp[1]-- ;
	cout << n-dinic()-mp[1] ;
	return 0 ;
}