HDOJ Uniform Generator：排序與隨機數生成器的優化解法

問題背景

HDOJ 的 Uniform Generator 題目要求判斷一個線性同餘生成器產生的序列是否能覆蓋 0 到 mod-1 的所有整數。若能覆蓋則為 "Good Choice"，否則為 "Bad Choice"。這類問題常見於隨機數生成器的週期性分析。

核心思路

採用「打表 + 排序 + 比較」的策略：

1. 預先生成一個包含 0 到 99999 的有序陣列 list 作為基準。
2. 對每組輸入的 step 和 mod，利用遞推公式 radom[i] = (radom[i-1] + step) % mod 生成序列。
3. 對生成的序列進行快速排序（qsort）。
4. 將排序後的序列與基準陣列逐一比較，若完全一致則輸出 "Good Choice"，否則輸出 "Bad Choice"。

關鍵代碼片段

#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
using namespace std;

const int maxn = 100000;
int list[maxn], radom[maxn];

void Makelist() {
    for (int i = 0; i < maxn; i++) list[i] = i;
}

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int step, mod;
    Makelist();
    while (cin >> step >> mod) {
        int flag = 1;
        memset(radom, 0, sizeof(radom));
        radom[0] = 0;
        for (int i = 1; i < mod; i++)
            radom[i] = (radom[i-1] + step) % mod;

        qsort(radom, mod, sizeof(int), cmp);

        for (int i = 0; i < mod; i++) {
            if (list[i] != radom[i]) {
                flag = 0;
                break;
            }
        }

        cout << setw(10) << step << setw(10) << mod << " "
             << (flag ? "Good Choice" : "Bad Choice") << endl << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(mod log mod)，主要來自排序。
• 空間複雜度：O(maxn)，約 400 KB，符合題目限制。

常見陷阱

注意 qsort 的第三個參數應為 sizeof(int) 而非 sizeof(mod)，否則會導致排序錯誤。此外，輸出格式需嚴格遵循 setw(10) 對齊，並在每組結果後輸出空行。