嘟嘟嘟
这不就是个bsgs板儿嘛。
顺便就复习了一下bsgs和哈希表。
头一次觉得我的博客这么好用，一下就懂了：数论学习笔记之高次不定方程
这里再补充几点：
1.关于这一段代码：
int S = sqrt(c), p = 1;
for(int i = 0; i < S; ++i)
{
if(p == b) return i + cnt;
insert(1LL * p * b % c, i);
p = 1LL * p * a % c;
}
for(int i = S, q = p; i - S + 1 < c; i += S)
{
int t = query(q);
if(~t) return i - t + cnt;
q = 1LL * q * p % c;
}
这一段是bsgs里最核心的部分。
首先是为什么(q)每一次乘以(p)：第一层循环后，(p)就成为了(a ^ m)，这样就相当于(a ^ {i * m})。
然后是第二层循环的终止条件为什么是这个：大家都知道，这一段代码是枚举(a ^ {tm})的，只不过用(i)代替了(tm)，所以我们考虑(i)的最大值：(tm - y < c Rightarrow i - (m - 1) < c Rightarrow i - m + 1 < c) 。这就出来了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int base = 99979;
const int maxe = 1e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int g, P, n;
In ll quickpow(ll a, ll b, ll mod)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}
In ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
In void exgcd(ll a, ll b, ll& x, ll& y)
{
if(!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= a / b * x;
}
In ll inv(ll a, ll mod)
{
ll x, y;
exgcd(a, mod, x, y);
return x;
}
struct Hash
{
int nxt, to, w;
}e[maxe];
int head[base], ecnt = 0;
int st[base], top = 0;
In void init()
{
ecnt = 0;
while(top) head[st[top--]] = 0;
}
In void insert(int x, int y)
{
int h = x % base;
if(!head[h]) st[++top] = h;
e[++ecnt] = (Hash){head[h], x, y};
head[h] = ecnt;
}
In int query(int x)
{
int h = x % base;
for(int i = head[h]; i; i = e[i].nxt)
if(e[i].to == x) return e[i].w;
return -1;
}
In int bsgs(int a, int b, int c)
{
int Gcd, d = 1, cnt = 0;
while((Gcd = gcd(a, c)) ^ 1)
{
if(b % Gcd) return -1;
++cnt; b /= Gcd, c /= Gcd;
d = 1LL * d * (a / Gcd) % c;
}
b = 1LL * b * inv(d, c) % c;
init();
int S = sqrt(c), p = 1;
for(int i = 0; i < S; ++i)
{
if(p == b) return i + cnt;
insert(1LL * p * b % c, i);
p = 1LL * p * a % c;
}
for(int i = S, q = p; i - S + 1 < c; i += S)
{
int t = query(q);
if(~t) return i - t + cnt;
q = 1LL * q * p % c;
}
return -1;
}
int main()
{
g = read(), P = read(), n = read();
for(int i = 1; i <= n; ++i)
{
int A = read(), B = read();
write(quickpow(g, 1LL * bsgs(g, A, P) * bsgs(g, B, P) , P)), enter;
}
return 0;
}