积木 ## 来源 University of Waterloo Local Contest 2002.09.21 (ZOJ1910, POJ2363) ## 题目描述 Donald想给他的小侄子送礼物。Donald是一个传统的人，他给他的小侄子选择了一套积木。这套积木共N个，每个积木都是一个立方体，长宽高都是1英寸。Donald想把这些积木放到一个长方体里，用牛皮纸包装起来拖运，请问，Donald至少需要多大的牛皮纸？ ## 输入描述 输入文件的第1行为一个整数C，代表测试数据的数目。每个测试数据占一行，为一个正整数N，表示需要包装的积木数目。N不超过1000。 ## 输出描述 对每个测试数据，输出占一行，为包装这N个积木需要牛皮纸的最小面积，单位为平方英寸。 ## 样例输入 ```txt 2 9 26 ``` ## 样例输出 ```txt 30 82 ``` ## 提示 题目的意思是要使得N个积木“堆满”整个长方体，不能有“空隙”。 假设长方体的长宽高分别为a、b、c（均为整数）；枚举长方体的长度a，a的取值从1开始取，直到a*a*a>N为止；注意，这里不能用a<=pow(N,1.0/3)，因为浮点数无法精确表达，当N=64时，pow(N,1.0/3)的值可能为3.9999999999999996，而不是4；对a的每个取值，枚举长方体的宽度b，b的取值从a开始，最大不能使得a×b×b>N；对a和b的每一对取值，如果N%(a*b)不为0，则跳过，否则c = N/(a*b)，从而求长方体的表面积。在枚举过程取最小的。 N = 26时枚举过程如下图所示。a取值为1：b取值为1时，c为26，此时表面积为106；b取值为2时，c为13，此时表面积为82。按照上述方法枚举时，a、b、c的其他取值都不能使得26块积木堆满一个长方体，因此最小面积为82。