POJ 2769：同餘與暴力枚舉最小模數

問題描述

給定 n 個整數，找最小的正整數 m，使得這 n 個數對 m 取模的結果兩兩不同。n ≤ 100，數值 ≤ 10^5。

解題思路

暴力枚舉 m 從 1 開始，對每個 m 檢查所有數取模後是否有重複。由於答案 m 不會超過 max(數值)+1（鴿巢原理），上界可設為 100000。檢查時用布爾數組或 bitset 記錄模值是否出現，O(n) 判斷。總複雜度 O(m_max * n) ≈ 10^7，可接受。

代碼實現 (C++)

#include 
using namespace std;
const int MAXM = 100001;
int a[105], seen[MAXM];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        int m;
        for (m = 1; m < MAXM; ++m) {
            fill(seen, seen+m, 0);
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                int r = a[i] % m;
                if (seen[r]) { ok = false; break; }
                seen[r] = 1;
            }
            if (ok) { printf("%d\n", m); break; }
        }
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(M * n)，M 為答案上界（≤ 10^5），n ≤ 100。
• 空間複雜度：O(M)。

總結

本題利用鴿巢原理確定枚舉上界，配合標記數組快速去重判斷，暴力枚舉即可通過。注意數組大小設置為答案上界而非數值上界可節省時間。