Description

题库链接

给出 \(A,B,P,g\) ，\(g\) 是 \(P\) 的原根，求出 \(A\equiv g^a\pmod{P}\) ， \(B\equiv g^b\pmod{P}\) 中的 \(a,b\) ，并输出 \(g^{ab}\) 。

\(2\leq A,B<P<2^{31},2\leq g<20,1\leq n\leq 20\)

Solution

\(BSGS\) 板子啊，由于 \(g\) 是 \(P\) 原根，解是唯一的。

Code

#include <bits/stdc++.h>

using namespace std;

map<int, int>mp;

int g, p, n, a, b;

int quick_pow(int a, int b) {

    int ans = 1;

    while (b) {

        if (b&1) ans = 1ll*ans*a%p;

        b >>= 1, a = 1ll*a*a%p;

    }

    return ans;

}

int BSGS(int a, int b) {

    mp.clear();

    int lim = ceil(sqrt(p)), cnt = b%p;

    for (int i = 0; i <= lim; i++, cnt = 1ll*cnt*a%p)

        mp[cnt] = i;

    int t = cnt = quick_pow(a, lim);

    for (int i = 1; i <= lim; i++, cnt = 1ll*cnt*t%p)

        if (mp.count(cnt)) return lim*i-mp[cnt];

}

void work() {

    scanf("%d%d%d", &g, &p, &n);

    while (n--) {

        scanf("%d%d", &a, &b);

        a = BSGS(g, a); printf("%d\n", quick_pow(b, a)) ;

    }

}

int main() {work(); return 0; }