#include #include #define INF 0x7FFFFFFF using namespace std; int main(){ long long n;//立方体をn個の合同な直方体に分割したい。 cin >> n; /* 合同にするには必ず、X→Y→Z軸にそって等分していかないとだめでは? 三回だけしか等分割できない→ 解き方: Tmax = n-1なので、Tminが問題。 Tmin は N = abcと分解できる時の、 a + b + c -3 の最小値 ここでaは a * a * a <= Nを満たすはずなので総当りでも解けるということ。 */ long long Tmin = n-1,Tmax = n-1; long long a = 1, b = 1, c = 1; int count = 0; long long tmp; for(a = cbrt(n)+1; a > 0; a--){ //b,cを総当りする。bc = n/aとあらわせる。 if(n % a != 0) continue; for(b = sqrt(n/a)+1; b > 0; b--){ if((n/a) % b != 0) continue; tmp = a + b + n/a/b -3; //cout << tmp << endl; if(tmp < Tmin){ Tmin = tmp; // cout << count << "change" << endl; } } } cout << Tmin << " " << Tmax << endl; return 0; } /* N = a*b*c において a+b+c-3の最小値を求める */