题解
BSGS直接解出a和b来即可
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pdi pair<db, int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 1000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template <class T>
void read(T &res) {
res = 0;
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template <class T>
void out(T x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int P, g, S;
int inc(int a, int b) { return a + b >= P ? a + b - P : a + b; }
int mul(int a, int b) { return 1LL * a * b % P; }
int fpow(int x, int64 c) {
int res = 1, t = x;
while (c) {
if (c & 1) res = mul(res, t);
t = mul(t, t);
c >>= 1;
}
return res;
}
struct node {
int x, p, next;
} E[100005];
int head[mo + 5], sumE;
void add(int x, int p) {
int u = x % mo;
E[++sumE].next = head[u];
E[sumE].x = x;
E[sumE].p = p;
head[u] = sumE;
}
int Query(int x) {
int u = x % mo;
for (int i = head[u]; i; i = E[i].next) {
if (E[i].x == x) return E[i].p;
}
return -1;
}
int64 BSGS(int A, int C) {
sumE = 0;
memset(head, 0, sizeof(head));
int t = 1;
for (int i = 0; i < S; ++i) {
if (t == C) return i;
add(mul(t, C), i);
t = mul(t, A);
}
int h = t;
for (int i = 1;; ++i) {
int x = Query(h);
if (x != -1) return 1LL * i * S - x;
h = mul(h, t);
if (i > P / S) break;
}
}
void Solve() {
int A, B;
read(A);
read(B);
int64 a = BSGS(g, A), b = BSGS(g, B);
out(fpow(g, a * b % (P - 1)));
enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in", "r", stdin);
#endif
read(g);
read(P);
S = sqrt(P);
int T;
read(T);
while (T--) {
Solve();
}
return 0;
}