ZeroJudge 解題筆記：d183. 00725 - Division

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


ZeroJudge 題目連結：d183. 00725 - Division

解題想法

題目要求將 $0$ 到 $9$ 分配成兩個 $5$ 位數 $a, b$，而且開頭可以為 $0$，代表可能的數字下限為 $1234$、上限為 $98765$，而且 $a$ 可以整除 $b$，商為 $2$ 到 $79$，所以 $a$ 的範圍大約是 $1234$ 到 $49876$， $b$ 的範圍大約是 $49876$ 到 $98765$。另外再寫兩個自訂函式，檢查兩個數是否有重覆的數字。建表，計算商為 $2$ 到 $79$ 可能的除數、被除數組合，再查表找答案。 用 Python 的 itertools.permutations 也可以窮舉所有數字的組合，但這樣會多跑很多不可能的數字，速度會比較慢。

Python 程式碼

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

import sys

def check_self(s):
    """ 代入字串，檢查是否有重複的數字 """
    used = set()  # 已經出現的數字
    for c in s:  # 依序讀取字元 c
        if c in used:  # 如果 c 已經出現過
            return False  # 回傳 False
        used.add(c)  # c 加入 used
    return True  # 如果可以跑到這行，回傳 True

def check_other(s, t):
    """ 代入字串 s, t，檢查是否有重複的數字 """
    used = set(list(s))  # s 已經檢查過，直接轉成 set
    for c in t:  # 依序讀取字元 c
        if c in used:  # 如果 c 已經出現過
            return False  # 回傳 False
        used.add(c)  # c 加入 used
    return True  # 如果可以跑到這行，回傳 True

""" 建表 """
low, mid, high = 1234, 49876, 98765  # 除數下限、上限，被除數上限
table = [[] for _ in range(80)]  # 表格，各種商的組合
for a in range(low, mid+1):  # 依序測試可能的除數 a
    n = str(a).zfill(5)  # 轉成字串，前面補 0 至 5 位數
    if not check_self(n): continue  # 如果 n 有重複的數字，找下一個
    for i in range(2, 80):  # 依序測試可能的倍數 i
        b = a*i  # 被除數 b
        if b >= high: break  # 如果 b 超過上限，不可能再有解，中止迴圈
        m = str(b).zfill(5)  # 轉成字串，前面補 0 至 5 位數
        if check_self(m) and check_other(n, m):  # 如果 m 本身、m 與 n 沒有重複的數字
            table[i].append((m, n))  # (m, n) 加到 table[i]

""" 讀取測資，組合答案 """
result = []
for line in sys.stdin:
    N = int(line)
    if N == 0: break
    if result: result.append("\n")  # 如果 result 已經有內容，先換行
    if not table[N]:  # 如果 table[N] 是空的，無解
        result.append(f"There are no solutions for {N:d}.\n")
    else:  # 反之，依序讀取 table[N] 的內容組成答案
        for t in table[N]:
            result.append(f"{t[0]} / {t[1]} = {N:d}\n")
sys.stdout.write("".join(result))

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

import sys, itertools

table = [[] for _ in range(80)]
nums = tuple(map(str, range(10)))
for a in itertools.permutations(nums, 5):
    s = "".join(a)
    n = int(s)
    b = [i for i in map(str, range(10)) if i not in a]
    for c in itertools.permutations(b, 5):
        t = "".join(c)
        m = int(t)
        if n < m: break  # 剪枝，接下來不可能有答案
        if n%m == 0:
            table[n//m].append((s, t))

result = []
for line in sys.stdin:
    N = int(line)
    if N == 0: break
    if result: result.append("\n")
    if not table[N]:
        result.append(f"There are no solutions for {N:d}.\n")
    else:
        for t in table[N]:
            result.append(f"{t[0]} / {t[1]} = {N:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;

bool check_self(string s) {
    /* 代入字串，檢查是否有重複的數字 */
    set<char> used;  // 已經出現的數字
    for(char c : s) {  // 依序讀取字元 c
        if (used.count(c) == 1) {  // 如果 c 已經出現過
            return false;  // 回傳 false
        }
        used.insert(c);  // c 加入 used
    }
    return true;  // 如果可以跑到這行，回傳 true
}

bool check_other(string s, string t) {
    /* 代入字串 s, t，檢查是否有重複的數字 */
    set<char> used;  // s 已經檢查過，直接轉成 set
    for(char c : s) used.insert(c);
    for(char c : t) {  // 依序讀取字元 c
        if (used.count(c) == 1) {  // 如果 c 已經出現過
            return false;  // 回傳 false
        }
        used.insert(c);  // c 加入 used
    }
    return true;  // 如果可以跑到這行，回傳 true
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    /* 建表 */
    // 除數下限、上限，被除數上限
    const int low = 1234, mid = 49876, high = 98765;
    vector<vector<vector<string>>> table (80);  // 表格，各種商的組合
    for(int a=low; a<=mid; a++) {  // 依序測試可能的除數 a
        string n = to_string(a);  // 轉成字串，前面補 0 至 5 位數
        while(n.size() < 5) n = "0" + n;
        if (!check_self(n)) continue;  // 如果 n 有重複的數字，找下一個
        for(int i=2; i<80; i++) {  // 依序測試可能的倍數 i
            int b = a*i;  // 被除數 b
            if (b >= high) break;  // 如果 b 超過上限，不可能再有解，中止迴圈
            string m = to_string(b);  // 轉成字串，前面補 0 至 5 位數
            while(m.size() < 5) m = "0" + m;
            if (check_self(m) && check_other(n, m)) {  // 如果 m 本身、m 與 n 沒有重複的數字
                table[i].push_back({m, n});  // {m, n} 加到 table[i]
            }
        }
    }
    /* 讀取測資，組合答案 */
    bool first = true;
    int N;
    while(cin >> N && N != 0) {
        if (first) {  // 如果是第一筆測資，first 設定成 false
            first = false;
        } else {
            cout << "\n";  // 如果不是第一筆測資，先換行
        }
        if (table[N].empty()) {  // 如果 table[N] 是空的，無解
            cout << "There are no solutions for " << N << ".\n";
        } else {  // 反之，依序讀取 table[N] 的內容組成答案
            for(auto t : table[N]) {
                cout << t[0] << " / " << t[1] << " = " << N << "\n";
            }
        }
    }
    return 0;
}