TPC追いコン : D - 幾何問題を書こう

なんか段々簡単になっていくのですが…。
http://oidashi.contest.atcoder.jp/tasks/oidashi_d

問題

N個の球がある。
各球の体積はV[i]である。

これらの球に内包される最大の立方体の1辺を考える。
この辺の長さに実数rを掛算した値を有理数にしたい。

N個の球に対し同じrを適用したとき、有理数に出来るものは最大何個あるか。

解法

V[i]から真面目に立方体の1辺を計算する必要はない。
rは実数なので、π等の定数項はrを最適に選べばうまく消える。

そこで、この問題は以下のように言い換えることができる。

• V[i]の三乗根にrを掛けて整数にしたい。最適にrを選択したとき、N個中最大何個整数に出来るか。

V[i]=R[i]*(p[i]^3)と表現する。
p[i]はR[i]が整数となるような最大の整数値とする。

とすると、V[i]にはR[i]^2を掛ければ三乗根が整数になる。
逆にR[i]が異なる球同士に同じ値を掛けても、両方三乗根を整数にすることはできない。
後はR[i]の登場回数の最大値を求めればよい。

p[i]を求めるのに、V[i]を2から順にV[i]の三乗根まで割っていこうとするとTLEする。
素数でだけ割るようにするとか、先に素数の三乗を計算するなど、計算回数を減らすなどの工夫が必要。

int N;
ll V[101010];
ll C[101010];
ll R[101010];

const int prime_max = 100000;
int NP,divp[prime_max];
ll prime[100000];

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

map<ll,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	FOR(i,NP) prime[i]=prime[i]*prime[i]*prime[i];
	
	cin>>N;
	int ma=0;
	FOR(i,N) {
		cin>>V[i];
		FOR(j,NP) {
			if(prime[j]>V[i]) break;
			while(V[i]%prime[j]==0) V[i]/=prime[j];
		}
		M[V[i]]++;
		ma=max(ma,M[V[i]]);
	}
	
	cout<<ma<<endl;
}

まとめ

こんな安直でいいのかなと思ったけど、通ってしまった。