HDU 1226：超級密碼——BFS 構造最小滿足條件的 C 進制數

問題大意

給定十進制整數 N (0 ≤ N ≤ 5000)、進制 C (2 ≤ C ≤ 16) 和 M 個可用數字。求最小的正整數（以 C 進制表示），僅由給定數字組成，且是 N 的倍數。密碼長度不超過 500 位，否則輸出 give me the bomb please。

核心思路：BFS + 取模狀態壓縮

數字極長，不可用整型存儲。利用同餘原理：僅需記錄「當前數字對 N 的餘數」。從高位到低位構造，BFS 保證最先找到的是長度最短、字典序最小的解。

狀態定義

• 節點：{當前字符串, 當前餘數}
• 初始狀態：所有非零可用數字（避免前導零）。
• 轉移：對每個可用數字 d，新餘數 (old_mod * C + d) % N。
• 訪問標記 vis[mod]：同一餘數只保留最短路徑。
• 終止條件：餘數為 0，輸出對應字符串。

關鍵代碼片段 (C++)

struct Node { string ans; int mod; };
queue<Node> q;
int vis[5005], a[16]; // a[i]=1 表示數字 i 可用

void bfs() {
    // 初始化：非零數字入隊
    for (int i = 1; i < 16; ++i) if (a[i]) {
        int mod = i % n;
        if (!vis[mod]) {
            vis[mod] = 1;
            q.push({char(i<10?'0'+i:'A'+i-10), mod});
        }
    }
    string best;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.mod == 0) { // 找到答案
            if (best.empty() || cur.ans.size() < best.size() || 
                (cur.ans.size() == best.size() && cur.ans < best))
                best = cur.ans;
            continue;
        }
        if (!best.empty() && cur.ans.size() >= best.size()) continue; // 剪枝
        for (int i = 0; i < 16; ++i) if (a[i]) {
            int nmod = (cur.mod * c + i) % n;
            if (!vis[nmod] && cur.ans.size() + 1 <= 500) {
                vis[nmod] = 1;
                q.push({cur.ans + char(i<10?'0'+i:'A'+i-10), nmod});
            }
        }
    }
    if (best.empty()) puts("give me the bomb please");
    else cout << best << '\n';
}

特殊情況處理

• N = 0：任何數都是 0 的倍數，最小解為單個數字 0（若 0 可用），否則無解。
• 長度限制 500：BFS 層序遍歷天然保證最短，超長直接剪枝。

複雜度分析

• 狀態數 ≤ N (≤ 5000)，每狀態最多嘗試 16 個數字。
• 時間 O(N * C)，空間 O(N + 答案長度)，完全滿足限制。