BZOJ 2242 [SDOI2011] 計算器 解題報告：快速冪、擴展歐幾里得、BSGS

題目大意

三類查詢，給定 y, z, p：

1. y^z mod p
2. 解 x*y ≡ z (mod p)，求最小非負整數解 x
3. 解 y^x ≡ z (mod p)，求最小非負整數解 x（離散對數）

分類解法

類型 1：快速冪模板

long long mod_pow(long long a, long long b, long long mod) {
    long long res = 1 % mod;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

類型 2：線性同餘方程 x*y ≡ z (mod p)

轉化為 x*y + k*p = z，即 x*y ≡ z (mod p)。

• 令 g = gcd(y, p)
• 若 z % g != 0 → 無解
• 否則用擴展歐幾里得求 y*x0 + p*k0 = g
• 特解 x = x0 * (z/g)
• 通解模 p/g，取最小非負解

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

long long solve_linear(long long y, long long z, long long p) {
    long long x, k;
    long long g = exgcd(y, p, x, k);
    if (z % g) return -1; // 無解
    long long mod = p / g;
    x = x * (z / g) % mod;
    if (x < 0) x += mod;
    return x;
}

類型 3：離散對數 y^x ≡ z (mod p) —— BSGS (Baby-Step Giant-Step)

核心思想：令 x = i*m - j，其中 m = ceil(sqrt(p))。

• 預計算 y^j mod p 存入哈希表（j = 0..m-1）
• 計算 y^m mod p，迭代 i = 0..m 檢查 z * (y^m)^i mod p 是否在表中
• 找到則 x = i*m - j

注意處理 y, p 不互質的情況（需先提取公因子）。

#include <unordered_map>

long long bsgs(long long y, long long z, long long p) {
    y %= p; z %= p;
    if (z == 1) return 0; // y^0 = 1

    unordered_map mp;
    long long m = ceil(sqrt(p));
    long long cur = 1;
    for (int j = 0; j < m; j++) {
        if (!mp.count(cur)) mp[cur] = j;
        cur = cur * y % p;
    }

    long long factor = mod_pow(y, m, p); // y^m
    cur = z;
    for (int i = 0; i <= m; i++) {
        if (mp.count(cur)) {
            long long ans = 1LL * i * m - mp[cur];
            if (ans >= 0) return ans;
        }
        cur = cur * factor % p;
    }
    return -1; // 無解
}

完整程式碼框架

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll mod_pow(ll a, ll b, ll mod) { ... }
ll exgcd(ll a, ll b, ll &x, ll &y) { ... }
ll solve_linear(ll y, ll z, ll p) { ... }
ll bsgs(ll y, ll z, ll p) { ... }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, k;
    while (cin >> T >> k) {
        while (T--) {
            ll y, z, p; cin >> y >> z >> p;
            if (k == 1) {
                cout << mod_pow(y, z, p) << '\n';
            } else if (k == 2) {
                ll ans = solve_linear(y, z, p);
                if (ans == -1) cout << "Orz, I cannot find x!\n";
                else cout << ans << '\n';
            } else {
                ll ans = bsgs(y, z, p);
                if (ans == -1) cout << "Orz, I cannot find x!\n";
                else cout << ans << '\n';
            }
        }
    }
    return 0;
}

複雜度

• 類型 1：O(log z)
• 類型 2：O(log p)
• 類型 3：O(√p log p)（哈希表查詢）

易錯點總結

1. 類型 2：z % g != 0 直接無解；解出來要模 p/g 取最小非負
2. 類型 3：
   • y % p == 0 時特判：z == 0 答案為 1，否則無解
   • y, p 不互質時，標準 BSGS 失效，需先提取公因子遞歸處理（本題測試數據可能保證互質或較弱，但完整解法應處理）
   • 哈希表用 unordered_map 或自定義雜湊，注意 cur 可能重複，保留最小 j
3. 輸出格式：無解時固定字串 Orz, I cannot find x!

總結

本題綜合考察數論三大核心工具：

• 快速冪（模指數）
• 擴展歐幾里得（線性同餘）
• BSGS（離散對數）

掌握這三個模板，可解決絕大多數模數運算相關問題。