题意分析

给定$N$个$1 \times 1 \times 1$的立方体，将它们堆成一个长方体，求该长方体的最小表面积（即所需包装纸的最小面积）。

解题思路

1. 数学转化：长方体的表面积公式为$2(ab + bc + ca)$，其中$a,b,c$是长、宽、高，且满足$a \times b \times c = N$。
2. 优化目标：在所有可能的长方体组合中，找到使$2(ab + bc + ca)$最小的$a,b,c$。
3. 关键性质：当$a,b,c$最接近（即长方体最接近立方体）时，表面积最小。

解题步骤

1. 枚举所有可能的长、宽、高组合：
   • 遍历$a$（$1 \leq a \leq \sqrt[3]{N}$），保证$a \leq b \leq c$以减少重复计算。
   • 对于每个$a$，遍历$b$（$a \leq b \leq \sqrt{N/a}$），确保$b$合理。
   • 计算$c = N/(a \times b)$，并检查$c$是否为整数。
2. 计算表面积：对每个合法的$(a,b,c)$组合，计算$2(ab + bc + ca)$。
3. 记录最小值：在所有合法组合中，保留最小的表面积作为答案。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int C;
    cin >> C;
    
    for (int i = 0; i < C; ++i) {
        int N;
        cin >> N;
        
        int min_area = 2 * N + 2 * N;  // 初始化为最大可能值，例如1x1xN的情况
        
        // 遍历所有可能的a, b, c组合
        for (int a = 1; a * a * a <= N; ++a) {
            if (N % a != 0) continue;
            
            int M = N / a;
            for (int b = a; b * b <= M; ++b) {
                if (M % b != 0) continue;
                
                int c = M / b;
                
                // 计算当前组合的表面积
                int area = 2 * (a * b + a * c + b * c);
                
                // 更新最小表面积
                if (area < min_area) {
                    min_area = area;
                }
            }
        }
        
        cout << min_area << endl;
    }
    
    return 0;
}