yukicoder : No.376 立方体のN等分 (2)

終盤5問目をあきらめて先にこちらを書いていました。
http://yukicoder.me/problems/547

問題

直方体を平面で何度か切断して分割し、合同なN個の直方体を作りたい。
切断回数の最大・最小値を求めよ。

解法

各辺を(a-1),(b-1),(c-1)回の計(a+b+c-3)回切断すると、a*b*c個の長方形ができる。
よってa*b*c=Nの範囲でa+b+cの最大・最小値を求めよう。

a≦b≦cとする。
a+b+cが最大になるのは明らかにa=b=1,c=Nで、その際の切断回数はN-1である。
あとは最小切断回数の方を考えよう。

a,b,cはNの約数しかありえないので、先にNの約数を列挙し、２重ループでa,bを総当たりするとよい。
a,bが決まればcも決まるので、(a+b+c-3)の最小値を答えよう。

途中a*bがオーバーフローしたりしないよう気を付けること。

ll N;

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	auto v=enumdiv(N);
	ll mi=N-1;
	
	for(i=0;v[i]<=1000000 && v[i]*v[i]*v[i]<=N;i++) {
		for(j=i;v[j]<=100000000 && v[i]*v[j]*v[j]<=N;j++) if(N%(v[i]*v[j])==0) {
			mi=min(mi,v[i]+v[j]+N/v[i]/v[j]-3);
		}
	}
	
	cout<<mi<<" "<<(N-1)<<endl;
	
}

まとめ

そういえば久々のyukicoderだった気がする。