codevs 3249 搭积木
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
Petya有一个A×B×C的长方体积木，积木是有1×1×1的小积木块组成的。那么这个长方体的高为A，宽为B，长为C。(^-^哦亲，记住长方体的长不一定要比宽的数值大的哦)。
现在好玩Petya在这个长方体中的的左上角挖去了一个(A-1)×(B-2)×(C-2)的小长方体。并且告诉你被挖去长方体的体积为n，即n=(A-1)×(B-2)×(C-2)。现在问你被挖去后剩下的1×1×1的积木块最少和最多分别是多少个。
求min{A×B×C-n}和max{A×B×C-n}
输入描述 Input Description
输入共1行，仅一个正整数n。
输出描述 Output Description
输出共1行包含两个用空格隔开的正整数，表示最小剩余积木块和最大剩余积木块个数。
样例输入 Sample Input
7
样例输出 Sample Output
47 65
数据范围及提示 Data Size & Hint
对于20%的数据 n≤400
对于50%的数据 n≤10^6
对于100%的数据1 ≤ n≤10^9
1 /*这个题目直接n^2枚举会超时的，所以我们换一种枚举方式，枚举一条棱的时候，让他的^3<=n，这样我们也能去到所有的边长，然后在内层循环中让他们分别做长宽高就可以了，复杂度O（n的三分之二次幂），因为B，C都是-2，所以互换没什么意思，干脆不换*/ 2 #include<iostream> 3 using namespace std; 4 #include<cstdio> 5 #define ll long long 6 ll n,a,b,c; 7 ll minz=(1<<31)-1,maxz=0; 8 int main() 9 { 10 cin>>n; 11 for(a=1;a*a*a<=n;++a) 12 { 13 if(n%a==0) 14 { 15 for(b=1;a*b*b<=n;++b) 16 if(n%(a*b)==0) 17 { 18 c=n/(a*b); 19 minz=min(minz,(a+1)*(b+2)*(c+2)); 20 minz=min(minz,(a+2)*(b+1)*(c+2)); 21 minz=min(minz,(a+2)*(b+2)*(c+1)); 22 maxz=max(maxz,(a+1)*(b+2)*(c+2)); 23 maxz=max(maxz,(a+2)*(b+1)*(c+2)); 24 maxz=max(maxz,(a+2)*(b+2)*(c+1)); 25 26 } 27 } 28 } 29 cout<<minz-n<<" "<<maxz-n<<endl; 30 return 0; 31 }