ZeroJudge 解題筆記：d188. 11342 - Three-square

作者：王一哲
日期：2026年4月27日


ZeroJudge 題目連結：d188. 11342 - Three-square

解題想法

用字典建表，找出 $0$ 到 $50000$ 之間，由 $3$ 個非負完全平方數字相加的字典順序最小組合，最大只要測試到 $i = \sqrt{50000}$ 就好。用 3 層 for 迴圈建表，最外層跑 $i = 0$ 到 $i = \sqrt{50000}$，第 2 層跑 $j = i$ 到 $j = \sqrt{50000}$，第 3 層跑 $k = j$ 到 $k = \sqrt{50000}$，如果加總只要記錄第一次跑出來的 $i, j, k$ 就好。接下來讀取測資，查表，輸出答案。

Python 程式碼

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

def solve():
    import sys

    """ 建表，找出 0 ~ 50000 字典順序最小的組合 """
    max_k = 50000  # 題目的測資最大值
    max_i = int(max_k**0.5) + 1  # 可能的數字
    table = dict()  # 表格
    for i in range(max_i):  # 測試 i = 0 ~ max_i-1
        x = i*i  # 儲存 i 平方的值
        for j in range(i, max_i):  # 測試 j = 0 ~ max_i-1
            y = x + j*j  # 加上 j 平方，不能寫成 x += j*j，變數值會出問題
            if y > max_k: break  # 超過 max_k，中止迴圈
            for k in range(j, max_i):  # 測試 j = 0 ~ max_i-1
                z = y + k*k  # 加上 k 平方，不能寫成 y += k*k，變數值會出問題
                if z > max_k: break  # 超過 max_k，中止迴圈
                if z not in table:  # 如果 z 不在 table 之中
                    table[z] = (i, j, k)  # 設定為 (i, j, k)

    """ 讀取測資，輸出答案 """
    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])  # 要測試的數值 n
        ptr += 1
        if n not in table:  # 如果 n 不在 table 之中，印出 -1
            result.append("-1\n")
        else: # 反之，印出 table[n] 的值
            res = " ".join(map(str, table[n])) + "\n"
            result.append(res)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 0.1 s，記憶體約為 7.5 MB，通過測試。

#include <cstdio>
#include <map>
#include <vector>
using namespace std;

int main() {
    /* 建表，找出 0 ~ 50000 字典順序最小的組合 */
    const int max_k = 50000, max_i = 223;  // 題目的測資最大值、根號 max_k
    map<int, vector<int>> table;  // 表格
    for(int i=0; i<=max_i; i++) {  // 測試 i = 0 ~ max_i
        int x = i*i;  // 儲存 i 平方的值
        for(int j=i; j<=max_i; j++) {  // 測試 j = 0 ~ max_i
            int y = x + j*j;  // 加上 j 平方
            if (y > max_k) break;  // 超過 max_k，中止迴圈
            for(int k=j; k<= max_i; k++) {  // 測試 j = 0 ~ max_i
                int z = y + k*k;  // 加上 k 平方
                if (z > max_k) break;  // 超過 max_k，中止迴圈
                if (table.find(z) == table.end()) {  // 如果 z 不在 table 之中
                    table[z] = {i, j, k};  // 設定為 {i, j, k}
                }
            }
        }
    }
    /* 讀取測資，輸出答案 */
    int t; scanf("%d", &t);
    for(int i=0; i<t; i++) {
        int n; scanf("%d", &n);  // 要測試的數值 n
        if (table.find(n) == table.end()) {  // 如果 n 不在 table 之中
            puts("-1");  // 印出 -1
        } else {  // 反之，印出 table[n] 的值
            printf("%d %d %d\n", table[n][0], table[n][1], table[n][2]);
        }
    }
    return 0;
}

改用 unordered_map，速度快很多。使用時間約為 12 ms，記憶體約為 6.3 MB，通過測試。

#include <cstdio>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    /* 建表，找出 0 ~ 50000 字典順序最小的組合 */
    const int max_k = 50000, max_i = 223;  // 題目的測資最大值、根號 max_k
    unordered_map<int, vector<int>> table;  // 表格
    for(int i=0; i<=max_i; i++) {  // 測試 i = 0 ~ max_i
        int x = i*i;  // 儲存 i 平方的值
        for(int j=i; j<=max_i; j++) {  // 測試 j = 0 ~ max_i
            int y = x + j*j;  // 加上 j 平方
            if (y > max_k) break;  // 超過 max_k，中止迴圈
            for(int k=j; k<= max_i; k++) {  // 測試 j = 0 ~ max_i
                int z = y + k*k;  // 加上 k 平方
                if (z > max_k) break;  // 超過 max_k，中止迴圈
                if (table.find(z) == table.end()) {  // 如果 z 不在 table 之中
                    table[z] = {i, j, k};  // 設定為 {i, j, k}
                }
            }
        }
    }
    /* 讀取測資，輸出答案 */
    int t; scanf("%d", &t);
    for(int i=0; i<t; i++) {
        int n; scanf("%d", &n);  // 要測試的數值 n
        if (table.find(n) == table.end()) {  // 如果 n 不在 table 之中
            puts("-1");  // 印出 -1
        } else {  // 反之，印出 table[n] 的值
            printf("%d %d %d\n", table[n][0], table[n][1], table[n][2]);
        }
    }
    return 0;
}