BestCoder Round #49 1001：模運算最小選數 (DFS 枚舉子集)

問題描述

給定整數 a 和 n (≤20) 個整數 b_i。從中選若干數重新排序為 c_1..c_r，使 a % c_1 % c_2 ... % c_r = 0。求最小 r，無解輸出 -1。

關鍵觀察：模運算單調性

若 x % y % z 且 y ≤ z，則 x % y % z = x % y（因 x % y < y ≤ z）。故最優序列中 c_i 必**非遞增**。因此只需枚舉子集，按降序排列取模驗證。

算法：子集枚舉 + 剪枝

n ≤ 20，共 2^20 ≈ 1e6 子集，可行。對每個子集：

1. 提取元素，降序排序。
2. 模擬 val = a，依次 val %= c_i。
3. 若最終 val == 0，更新答案 min(ans, size)。

優化：DFS 搜索，按降序選擇，當前深度 ≥ 最佳答案時剪枝。

參考代碼 (C++ DFS)

#include 
using namespace std;
int n, a, b[20], ans;

void dfs(int idx, int curMod, int depth) {
    if (curMod == 0) { ans = min(ans, depth); return; }
    if (depth >= ans || idx == n) return;
    // 選 b[idx]
    dfs(idx + 1, curMod % b[idx], depth + 1);
    // 不選
    dfs(idx + 1, curMod, depth);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> n >> a;
        for (int i = 0; i < n; ++i) cin >> b[i];
        sort(b, b + n, greater()); // 降序，便於剪枝
        ans = INT_MAX;
        dfs(0, a, 0);
        cout << (ans == INT_MAX ? -1 : ans) << '\n';
    }
    return 0;
}

複雜度

最壞 O(2^n)，但剪枝極強（模運算快速收斂），實際極快。T ≤ 5 總時間毫秒級。

核心思想

• 模運算特性：x % y % z = x % y 若 y ≤ z，故最優序列非遞增。
• 將排序問題轉化為子集選擇問題，大幅減少搜索空間。
• DFS 深度優先 + 最優解剪枝是小規模組合優化標準套路。

總結

• 巧用數學性質簡化問題：非遞增序列 ↔ 子集枚舉。
• n=20 明示位掛/DFS 可行。
• 注意 a 初始值可能已為 0，但題目 a ≥ 1，無需特判。