BZOJ 2242 [SDOI2011] 計算器：模冪、擴展歐幾里得與 BSGS 完整解法

BZOJ 2242 [SDOI2011] 計算器：模冪、擴展歐幾里得與 BSGS 完整解法

題目要求三種模運算查詢（k=1,2,3）：

1. 模冪：給定 y, z, p，求 y^z mod p
2. 模線性方程：給定 y, z, p，求最小非負整數 x 滿足 x*y ≡ z (mod p)
3. 模離散對數：給定 y, z, p，求最小非負整數 x 滿足 y^x ≡ z (mod p)

子問題 1：快速冪模板

LL pow_mod(LL base, LL exp, LL mod) {
    LL ret = 1;
    base %= mod;
    while (exp) {
        if (exp & 1) ret = ret * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return ret;
}

時間複雜度 O(log z)，直接套用。

子問題 2：擴展歐幾里得求解線性同餘方程

方程 x*y ≡ z (mod p) ⇔ x*y + k*p = z（k 為整數）。

1. 計算 g = gcd(y, p)
2. 若 z % g != 0 → 無解
3. 用 exgcd(y, p) 求得 x0, y0 使 x0*y + y0*p = g
4. 特解 x = x0 * (z/g)
5. 通解 x = x + t*(p/g)，取模調整至 [0, p/g - 1] 即為最小非負解

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) { x = 1; y = 0; return a; }
    LL x1, y1;
    LL g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

子問題 3：BSGS (Baby-Step Giant-Step) 解離散對數

求 y^x ≡ z (mod p)，p 不一定為質數。

核心思想

• 設 x = i*m - j，其中 m = ceil(sqrt(p))
• y^(i*m) ≡ z * y^j (mod p)
• 預計算所有 j ∈ [0, m) 的 z * y^j mod p 存入哈希表
• 枚舉 i ∈ [1, m] 計算 y^(i*m) mod p 查表
• 找到匹配則 x = i*m - j 為解

代碼關鍵片段

LL m = ceil(sqrt(mod));
unordered_map<LL, LL> mp;  // value -> j
LL cur = z % mod;
for (LL j = 0; j < m; j++) {
    if (!mp.count(cur)) mp[cur] = j;
    cur = cur * y % mod;
}
LL factor = pow_mod(y, m, mod);  // y^m
cur = 1;
for (LL i = 1; i <= m; i++) {
    cur = cur * factor % mod;  // y^(i*m)
    if (mp.count(cur)) {
        LL j = mp[cur];
        LL ans = i * m - j;
        if (ans >= 0) return ans;
    }
}
return -1;  // 無解

注意：需處理 y、p 不互質情況（因子分解法），代碼中簡化假設互質或直接參考黃學長實現。

完整測試流程

讀 T
while T--:
    讀 k, y, z, p
    mod = p
    if k == 1: 輸出 pow_mod(y, z, p)
    if k == 2: 
        g = gcd(y, p)
        if z % g != 0: 輸出 "Orz, I cannot find x!"
        else: exgcd 求解輸出最小非負 x
    if k == 3: BSGS 求解輸出最小非負 x 或無解訊息

複雜度總結

心得

此題完美串聯數論三大核心工具：快速冪、擴展歐幾里得、BSGS。掌握三者模板與邊界處理（不互質、無解、大數取模），即可應對絕大多數模運算查詢問題。