POJ 3243 Clever Y：離散對數問題與 BSGS 算法詳解

問題背景

在數學中，給定底數 X、指數 Y 和模數 Z，計算 K = X^Y mod Z 是一個經典的模冪問題，可以用快速冪算法在 O(log Y) 時間內解決。但反過來，已知 X、Z、K，求最小的非負整數 Y 使得 X^Y ≡ K (mod Z)，這就是離散對數問題。POJ 3243 "Clever Y" 正是要求解這一問題。

核心思想：Baby-Step Giant-Step (BSGS)

BSGS 是解決離散對數的經典算法，時間復雜度為 O(√Z log Z)，空間復雜度 O(√Z)。基本思路是將指數 Y 表示為 Y = i·m - j，其中 m = ⌈√Z⌉，i, j ∈ [0, m)。原方程變為：

X^i·m ≡ K·X^j (mod Z)

先預計算所有 K·X^j mod Z（baby steps）並存入哈希表，再枚舉 i 計算 X^i·m mod Z（giant steps）查表匹配。找到匹配即得到解 Y = i·m - j。

關鍵實現細節

• 哈希表優化：使用自定義哈希表（鏈地址法）存儲 baby steps，鍵為值，值為 j，查找 O(1)。
• 邊界處理：若 K = 1 則 Y = 0；若 X = 0 需單獨討論。
• 無解判定：遍歷完所有 i 仍無匹配，輸出 "No Solution"。

代碼框架（C++）

const int MOD = 76543; // 哈希表大小，取質數
int hs[MOD], head[MOD], nxt[MOD], id[MOD], top;

void insert(int val, int idx) { ... }
int find(int val) { ... }

int BSGS(int a, int b, int n) {
    memset(head, -1, sizeof(head));
    top = 1;
    if (b == 1) return 0;
    int m = sqrt(n) + 1;
    long long x = 1, p = 1;
    for (int i = 0; i < m; ++i, p = p * a % n) {
        insert(p, i);
    }
    long long factor = p; // a^m mod n
    long long cur = b;
    for (int i = 1; i <= m; ++i) {
        cur = cur * factor % n;
        int j = find(cur);
        if (j != -1) return i * m - j;
    }
    return -1;
}

複雜度分析

時間 O(√Z log Z)，空間 O(√Z)。對於 Z ≤ 10⁹，√Z ≈ 31623，完全在限制內。

總結

BSGS 將指數問題轉化為空間換時間的查表問題，是解決大模數離散對數的標準方法。掌握其數學推導與工程實現細節（哈希表、模運算、邊界情況）對競賽編程至關重要。