POJ 3243 大步小步算法 (BSGS) 解題詳解：離散對數問題模板實現

問題描述

給定 X, Z, K（0 ≤ X,Z,K ≤ 10⁹），求最小非負整數 Y 使得 X^Y ≡ K (mod Z)。若無解輸出 "No Solution"。多測試用例，以 "0 0 0" 結束。

核心算法：Baby-Step Giant-Step (BSGS)

數學原理

設 Y = i·m + j，其中 m = ⌈√Z⌉。則：
X^{i·m + j} ≡ K (mod Z) ⇒ X^j ≡ K · (X^{-m})^i (mod Z)

1. Baby Steps：預計算 X^j mod Z (j=0..m) 存入哈希表
2. Giant Steps：枚舉 i=0..m，計算 K · (X^{-m})^i mod Z，查哈希表是否存在匹配的 j
3. 找到則 Y = i·m + j 為解，取最小者

關鍵細節處理

• 非互質情況：當 gcd(X, Z) ≠ 1 時，需提取公因子約簡。令 d = gcd(X, Z)，若 K % d ≠ 0 無解；否則方程兩邊同除 d，Z ← Z/d，K ← K/d，累積因子 D = D·X/d mod Z
• Y=0 特判：K ≡ 1 (mod Z) 時 Y=0
• 模逆元：使用擴展歐幾里得算法求 X^{-m} mod Z
• 哈希表：自定義開放寻址法，避免 STL unordered_map 常數開銷

完整 C++ 代碼（模板級）

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;

const int HASH_SIZE = 140000;
struct HashTable {
    struct Node { ll key, val, next; } e[HASH_SIZE];
    int head[HASH_SIZE], tot;
    void clear() { memset(head, -1, sizeof(head)); tot = 0; }
    void add(ll key, ll val) {
        if (find(key) != -1) return;
        int h = key % 65535;
        e[tot] = {key, val, head[h]};
        head[h] = tot++;
    }
    ll find(ll key) {
        int h = key % 65535;
        for (int i = head[h]; i != -1; i = e[i].next)
            if (e[i].key == key) return e[i].val;
        return -1;
    }
} hash_table;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
    if (!b) { d = a; x = 1; y = 0; return; }
    exgcd(b, a%b, d, y, x);
    y -= x * (a/b);
}

ll pow_mod(ll a, ll n, ll m) {
    ll res = 1; a %= m;
    while (n) { if (n&1) res = res*a%m; a = a*a%m; n >>= 1; }
    return res;
}

ll BSGS(ll A, ll B, ll C) {
    B %= C;
    ll tmp = 1; hash_table.clear();
    for (int i = 0; i <= 100; i++) {  // 小範圍直接檢查
        if (tmp == B) return i;
        tmp = tmp * A % C;
    }
    
    ll D = 1, d = 0;
    while ((tmp = gcd(A, C)) != 1) {
        if (B % tmp) return -1;
        C /= tmp; B /= tmp;
        D = D * A / tmp % C;
        d++;
    }
    
    ll m = (ll)ceil(sqrt((double)C));
    tmp = 1;
    for (int i = 0; i <= m; i++) {
        hash_table.add(tmp, i);
        tmp = tmp * A % C;
    }
    
    ll K = pow_mod(A, m, C);
    for (int i = 0; i <= m; i++) {
        ll x, y, dd;
        exgcd(D, C, dd, x, y);
        ll target = ((B * x) % C + C) % C;
        ll j = hash_table.find(target);
        if (j != -1) return i * m + j + d;
        D = D * K % C;
    }
    return -1;
}

int main() {
    ll A, B, C;
    while (cin >> A >> C >> B) {
        if (!A && !B && !C) break;
        ll ans = BSGS(A, B, C);
        if (ans == -1) cout << "No Solution" << endl;
        else cout << ans << endl;
    }
    return 0;
}

複雜度與適用場景

• 時間：O(√Z log Z) —— 主要在模冪與哈希操作
• 空間：O(√Z) —— 哈希表存儲 Baby Steps
• 適用：模數 Z ≤ 10⁹ 時極快，是離散對數問題標準解法

常見坑點

1. 輸入順序為 X Z K，代碼中參數對應 A=X, C=Z, B=K
2. K ≥ Z 時直接無解（模運算結果必 < Z）
3. 哈希表大小需 > √Z，建議 2~3 倍
4. 負數取模修正：((x%C)+C)%C

BSGS 是數論算法庫中的核心組件，掌握其非互質擴展版本可解決絕大多數離散對數問題。