ZeroJudge 解題筆記：r579.10365 - Blocks

作者：王一哲
日期：2026年9月7日


ZeroJudge 題目連結：r579.10365 - Blocks

解題想法

這題用窮舉法，但是要縮小測試的範圍，如果數量為 $n$，當長方體 $3$ 個邊長越接近時表面積越小，假設邊長為 $a, b, c$ 且 $a \leq b \leq c$，則 $a$ 的上限 $amax = \sqrt[3]{n} + 1$，第一層 for 迴圈跑 $a = 1$ 到 $a = amax$，如果 $a$ 不能整除 $n$ 就跑過；邊長 $b$ 的上限 $bmax = \sqrt{n/a}$，第二層 for 迴圈跑 $b = a$ 到 $b = bmax$，如果 $b$ 能夠整除 $n/a$，則 $c = n / (a \times b)$，表面積 $area = 2 \times (a \times b + b \times c + c \times a)$，更新答案 $ans$ 為新的最小值。

Python 程式碼

使用時間約為 21 ms，記憶體約為 9.4 MB，通過測試。

m = int(input())
for _ in range(m):
    n = int(input())
    ans = float('inf')  # 答案
    amax = int(n**(1/3))  # a 的上限為 n 開 3 次根號
    for a in range(1, amax + 2):  # 測試 a = 1 ~ amax + 1
        if n % a != 0: continue  # 不能整除，跳過
        bmax = int((n // a)**(1/2))  # b 的上限為 n/a 開根號
        for b in range(a, bmax + 1):  # 測試 a ~ bmax
            if (n // a) % b == 0:  # b 可以整除 n/a
                c = n // (a * b)  # c 的值
                ans = min(ans, 2 * (a*b + b*c + c*a))
    print(ans)

C 語言程式碼

使用時間約為 1 ms，記憶體約為 2 MB，通過測試。

#include <cstdio>
#include <cmath>

int main() {
    int m; scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        int n, ans = 1000000000;
        scanf("%d", &n);
        int amax = (int)cbrt(n);  // a 的上限為 n 開 3 次根號
        for(int a = 1; a < amax + 2; a++) {  // 測試 a = 1 ~ amax + 1
            if (n % a != 0) continue;  // 不能整除，跳過
            int bmax = (int)sqrt(n / a);  // b 的上限為 n/a 開根號
            for(int b = a; b < bmax + 1; b++) {  // 測試 a ~ bmax
                if ((n / a) % b == 0) {  // b 可以整除 n/a
                    int c = n / (a * b);  // c 的值
                    int area = 2 * (a*b + b*c + c*a);
                    if (area < ans) ans = area;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C++ 程式碼

使用時間約為 1 ms，記憶體約為 2 MB，通過測試。

#include <stdio.h>
#include <math.h>

int main() {
    int m; scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        int n, ans = 1000000000;
        scanf("%d", &n);
        int amax = (int)cbrt(n);  // a 的上限為 n 開 3 次根號
        for(int a = 1; a < amax + 2; a++) {  // 測試 a = 1 ~ amax + 1
            if (n % a != 0) continue;  // 不能整除，跳過
            int bmax = (int)sqrt(n / a);  // b 的上限為 n/a 開根號
            for(int b = a; b < bmax + 1; b++) {  // 測試 a ~ bmax
                if ((n / a) % b == 0) {  // b 可以整除 n/a
                    int c = n / (a * b);  // c 的值
                    int area = 2 * (a*b + b*c + c*a);
                    if (area < ans) ans = area;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}