好的，我们先明确题意与已知条件。

---

题意回顾

• 已知固定的质数 (P) 和原根 (g)。
• Alice 随机生成 (a)，发送 (A = g^a \bmod P)。
• Bob 随机生成 (b)，发送 (B = g^b \bmod P)。
• 密钥 (K = g^{ab} \bmod P)，Alice 算 (K = B^a \bmod P)，Bob 算 (K = A^b \bmod P)。

现在攻击者窃听到 (A) 和 (B)，知道 (g) 和 (P)，要算出 (K)。

---

问题本质

已知 (A \equiv g^a \pmod{P})，(B \equiv g^b \pmod{P})，
我们不知道 (a, b)，但要算出 (K \equiv g^{ab} \pmod{P})。

由于 (K \equiv A^b \equiv B^a \pmod{P})，
如果我们能求出 (a) 或 (b)，就能直接计算 (K)。

---

解法思路

从 (A = g^a \bmod P) 求 (a)，这是离散对数问题（DLP）。
给定 (P) 是质数，且 (g) 是原根，(a) 的范围是 (1) 到 (P-1)。

虽然 (P < 2^{31})，暴力枚举 (a) 最大需要 (O(P))，不行（(P) 最多约 (21) 亿）。

我们需要更快的算法。

---

Baby-step giant-step（BSGS）算法

对 (A \equiv g^a \pmod{P}) 求 (a)，用 BSGS 可以在 (O(\sqrt{P} \log P)) 时间求解。
由于 (P) 最大约 (2^{31})，(\sqrt{P} \approx 46340)，可行。

步骤：

1. 设 (m = \lceil \sqrt{P-1} \rceil)。
2. 预计算 (g^j \bmod P) 对 (j = 0,1,\dots,m-1)，存到哈希表（值 → 指数）。
3. 计算 (g^{-m} \bmod P)。
4. 令 (t = A)，对 (i=0) 到 (m-1)：
   • 检查 (t) 是否在表中，如果在且 (j) 对应，则 (a = i m + j)。
   • 更新 (t = t \cdot g^{-m} \bmod P)。

这样我们可以求出 (a) 或者 (b)，然后 (K = B^a \bmod P)。

---

优化

注意到我们并不需要同时求 (a) 和 (b)。
如果我们求出 (a)，那么 (K = B^a \bmod P)；
如果求出 (b)，那么 (K = A^b \bmod P)。

实际上，由于 (P) 固定，(g) 固定，我们可以对 (n) 次查询中的每个 (A) 求一次 (a)，然后算 (K)。

但是 BSGS 预计算只依赖 (g) 和 (P)，所以我们可以只做一次预计算，然后对每个 (A) 查询 (a)。

---

算法步骤

1. 读入 (g, P, n)。
2. 用 BSGS 预计算 (g^j \bmod P) 表（(j=0) 到 (m-1)）。
3. 对每个查询 ((A, B))：
   • 用 BSGS 从 (A) 求出 (a)。
   • 计算 (K = B^a \bmod P)。
   • 输出 (K)。

---

时间复杂度

• 预计算 (O(\sqrt{P})) 时间和空间。
• 每个查询 (O(\sqrt{P} \log P))（实际上用哈希表是 (O(\sqrt{P}))）。
• (n \le 20)，完全可行。

---

样例验证

样例：

3 31
3
27 16
21 3
9 26

1. 对 (A=27)，求 (a)：
   (3^a \equiv 27 \pmod{31})
   已知 (3^3 = 27)，所以 (a=3)。
   (K = 16^3 \bmod 31 = 4096 \bmod 31 = 4)。

2. 对 (A=21)，求 (a)：
   (3^a \equiv 21 \pmod{31})
   经计算 (3^{13} \bmod 31 = 21)，所以 (a=13)。
   (K = 3^{13} \bmod 31 = 21)。

3. 对 (A=9)，求 (a)：
   (3^a \equiv 9 \pmod{31})
   (3^2 = 9)，所以 (a=2)。
   (K = 26^2 \bmod 31 = 676 \bmod 31 = 25)。

输出 4, 21, 25，与样例一致。

---

实现细节

• 用 unordered_map 存储 (g^j \to j)。
• 用快速幂取模。
• 注意 (P) 在 int 范围内，但乘法可能溢出，要用 long long 做中间运算。

---

代码框架（C++）：

#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
using ll = long long;

ll powmod(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll discrete_log(ll g, ll A, ll P) {
    // BSGS, 返回 a 满足 g^a = A mod P
    ll m = ceil(sqrt(P));
    unordered_map<ll, ll> table;
    ll e = 1;
    for (ll j = 0; j < m; j++) {
        table[e] = j;
        e = e * g % P;
    }
    ll factor = powmod(g, P - 1 - m, P); // g^(-m) mod P
    e = A;
    for (ll i = 0; i < m; i++) {
        if (table.find(e) != table.end()) {
            return i * m + table[e];
        }
        e = e * factor % P;
    }
    return -1; // 不应该发生，因为 g 是原根且 A 在 [1,P-1]
}

int main() {
    ll g, P, n;
    cin >> g >> P >> n;
    while (n--) {
        ll A, B;
        cin >> A >> B;
        ll a = discrete_log(g, A, P);
        ll K = powmod(B, a, P);
        cout << K << endl;
    }
    return 0;
}

---

最终答案：
用 BSGS 求离散对数，然后快速幂算 (K)，对每组 (A,B) 输出。