読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Croc Champ 2013 - Round 2 : C. Cube Problem

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

問題

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

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

解法

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

ここで、(A+B+C)^3 - (A^3+B^3+C^3) = 3(A+B)(B+C)(C+A) = Nと変形できるので、まずNは3の倍数でなければならない。
A \le B \le Cという仮定を置き、X=A+B, Y=B+C, Z=C+Aと置き換えると、X^3 \le XYZ = \frac{N}{3}となる。
N \le 10^{14}なのでX \le 10^5程度で済むので、Xを全部列挙しよう。
次に、X^3 \le XY^2 \le XYZ = \frac{N}{3}なので、Xより大きいYを同様に列挙する。
XとYが求まればZ=\frac{N}{3XY}なので、Zも求まる。

ここでX \le Y \le 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;
}

まとめ

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

広告を非表示にする