先谈一下BSGS算法（传送门）
但是上面这位的程序实现比较繁琐，看下面这位的。
clover_hxy这样说
bsgs算法，又称大小步算法（某大神称拔山盖世算法）。
主要用来解决 A^x=B(mod C)(C是质数)，都是整数，已知A、B、C求x。（poj 2417 Discrete Logging）
具体步骤如下：
先把x=i*m-j，其中m=ceil(sqrt(C))，（ceil是向上取整）。
这样原式就变为A^(i*m-j)=B(mod C)，
再变为Aj×B=A(m*i) (mod C)。
枚举j(范围0-m),将A^j×B存入hash表
枚举i(范围1-m),从hash表中寻找第一个满足Aj×B=A(m*i) (mod C)。
此时x=i*m-j即为所求。
在网上看到的其他题解大多用的是x=i*m+j，也可以做，只是会牵扯的求逆元，所以比较麻烦。使x=i*m-j就可以轻松避免这个问题了。
那么肯定有人会有疑问为何只计算到m=ceil(sqrt(C))就可以确定答案呢？
x=i*m-j 也就是x 的最大值不会超过p,那超过p的怎么办 ？
有一个公式 a^(k mod p-1)=a^k (mod p) 这个公式的推导需要用到费马小定理
k mod p-1可以看做 k-m（p-1） ,原式可化成 ak/(a(p-1))m=ak (mod p)
根据费马小定理 a^(p-1)=1 (mod p) 其中p为质数 ，a,p 互质，可得ak/1m=a^k (mod p) ak=ak (mod p) 得证。
分析此题
实际上就是求 g^a = A (mod p) 中的a，于是顺利套出模板
注意，能少用pow我们就少用，尽量减少常数。本来就用了map，到时候被卡常就尴尬了
这题就等于模板题，没有什么特殊的需要处理
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int INF=0x7fffffff;
template<class T> inline T read(T&x){
T data=0;
int w=1;
char ch=getchar();
while(ch!='-'&&!isdigit(ch))
ch=getchar();
if(ch=='-')
w=-1,ch=getchar();
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
ll g,p,bl,A,B;
map <ll,ll> mp;
int pow1(ll x,ll k){
ll ans=1;
while(k>0)
{
if(k&1)
ans=(ans*x)%p;
x=(x*x)%p;
k>>=1;
}
return ans;
}
void init()
{
bl=ceil(sqrt(p));
ll cur=pow1(g,bl),ans=cur;
mp[ans]=bl;
for(ll i=2;i<=bl;++i)
{
ans=(ans*cur)%p;
mp[ans]=i*bl;
}
}
ll BSGS(ll x)
{
ll j=0,cur=1;
for(;j<=bl;++j)
{
if(mp[(cur*A)%p])
return mp[(cur*A)%p]-j;
cur=(cur*g)%p;
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(g);
read(p);
init();
ll n;
read(n);
while(n--)
{
read(A);
read(B);
printf("%lld\n",pow1(B,BSGS(A)));
}
// fclose(stdin);
// fclose(stdout);
return 0;
}