AtCoder AGC #003 : D - Anticube

まぁまぁ苦戦したけど何とか解けたので良かった。
http://agc003.contest.atcoder.jp/tasks/agc003_d

問題

N個の整数S[i]がある。
これらのうちの一部を選択する。
選択した要素群のうち、異なる２つS[a]とS[b]に対し、S[a]*S[b]が立方数であってはならない。

条件を満たす選び方のうち、最大何個まで選択できるか求めよ。

解法

まず、S[i] = P[i]*(Q[i]^2)*(R[i]^3)の形に分解できたとする。
P,Q,Rはそれぞれ素数を掛け合わせたもので、同じ素因数を持っていてはならない。
R[i]の値は、２要素の積を取る際立方数かどうかに影響しないので、以後S'[i] = S[i]/(R[i]^3) = P[i]*(Q[i]^2)について考える。

まず、S[i]がそもそも立方数であるもの、すなわちS'[i]=1のものを考える。
このような数値は、最大で1個しか選択できない。

S'[i]!=1となる要素について、S[a]*S[b]が立方数になるのはP[a]=Q[a]、Q[b]=P[b]の場合である。
逆にa∈A、b∈Bに対しP[a]=Q[a]、Q[b]=P[b]となる集合A,Bがあれば、これらはどちらかしか選択できないので大きな方を選択していけば良い。

ここまでわかると、後はS'[a]=P[a]*(Q[a]^2)に対し、P[a]=Q[b]、P[b]=Q[b]となるa,bの数を数え上げればいいことが分かった。
ただ、この問題はS[i]の値が大きく、R[i]はO(S[i]^(1/3))で列挙すれば間に合うがQ[i]をO(S[i]^(1/2))で列挙するとTLEする。
これを何とかしたい。

そこで、S'[a]から高速にP[a]・Q[a]を直接求める事なく、対となるQ[a]*(P[a]^2)を高速に計算することを考える。
それには(S'[a])^2=(P[a]^2)*(Q[a]^4)を求め、この数を立方数を総当たりして割ると(P[a]^2)*Q[a]が求められる。

int N;
ll S[101010];

const int prime_max = 100000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;

map<ll,int> PV;
set<ll> did;

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

ll hoge(ll n) {
	int i;
	FOR(i,NP) {
		ll a=prime[i];
		if(a>1000) break;
		
		while(n % (a*a*a)==0) n /= a*a*a;
	}
	return n;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cprime();
	int cube=0;
	FOR(i,N) {
		cin>>S[i];
		ll v=hoge(S[i]);
		if(v==1) cube++;
		else PV[v]++;
	}
	
	int ret=N;
	if(cube) ret -= (cube-1);
	FORR(r,PV) {
		if(did.count(r.first)) continue;
		ll rr=hoge(r.first*r.first);
		
		if(PV.count(rr)) ret -= min(r.second,PV[rr]);
		did.insert(rr);
	}
	cout<<ret<<endl;
	
}

まとめ

対になる数の求め方が思いついてよかった。