Croc Champ 2013 - Round 2 : C. Cube Problem

さてC。
http://codeforces.com/contest/293/problem/C

問題

１辺1の長さの立方体を組み合わせ、最初にA×A×AとB×B×BとC×C×Cの３つの立方体を作った。
その後、最初の３つを分解して、再度１辺が(A+B+C)の立方体を作ろうとしたところ、立方体が足りないのでN個追加し、1辺が(A+B+C)の立方体を作った。

Nが与えられるとき、A,B,Cの組み合わせ数を答えよ。

解法

自分では解けないというか、そもそも問題の意味を誤解してしており解ける気がしなかったためEditorialを見て挑戦。
この問題は、Nに対してとなるA,B,Cの組み合わせを求めよ、となる。

ここで、と変形できるので、まずNは３の倍数でなければならない。
という仮定を置き、と置き換えると、となる。
なので程度で済むので、Xを全部列挙しよう。
次に、なので、Xより大きいYを同様に列挙する。
XとYが求まればなので、Zも求まる。

ここでが満たされるならそれを答えとしてカウントする。
実際はA,B,Cは順不同なので、その分もカウントする。

XとYを律儀に計算するとTLEするので、先にNの約数を列挙しておき、XとYはその中を処理するようにすると良い。

ll N;

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin>>N;
	if(N%3) return (void)_P("0\n");
	N/=3;
	
	vector<ll> P;
	for(ll X=1;X*X<=N;X++) if(N%X==0) P.push_back(X);
	
	int ret=0;
	FOR(x,P.size()) for(y=x;y<P.size();y++) {
		if(N/(P[x]*P[y])<P[y]) break;
		if(N%(P[x]*P[y])==0) {
			ll Z=N/(P[x]*P[y]);
			ll a=P[x]+P[y]-Z,b=Z+P[x]-P[y],c=P[y]+Z-P[x];
			if(a>0 && b>0 && c>0 && (a%2==0) && (b%2==0) && (c%2==0)) {
				if(a==b && b==c) ret++;
				else if(a==b || b==c || c==a) ret+=3;
				else ret+=6;
			}
		}
	}
	
	_P("%d\n",ret);
	
	return;
}

まとめ

終わってみるとコードは短いな。