大雾
by 黑客 @ 2020-08-12 20:56:49
这是为什么？萌新求助
by 黑客 @ 2020-08-12 21:01:12
你这写法好诡异……看不懂
拔山盖世不是要Hash的吗
by Isprime @ 2020-08-12 21:01:12
BSGS应该是保证取值在根号p之内吧
by 黑客 @ 2020-08-12 21:01:48
@[Isprime](/user/149815) 我太菜了，用的是STL
by 黑客 @ 2020-08-12 21:02:14
@[黑客](/user/189394) 能不能放完整点的代码 /kk
by smarthehe @ 2020-08-12 21:21:14
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define in inline
#define mod p
ll p,g,m,n,A,B,a;
map<ll,ll>vis;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
int main(){
scanf("%lld%lld%lld",&g,&p,&n);
m=sqrt(p);
for(int i=0;i<=m+2;i++)vis[qpow(g,i*m)]=i*m;
while(n--){
scanf("%lld%lld",&A,&B);
for(int i=0;i<=m+1;i++){
ll t=(A*qpow(g,i))%mod;
if(vis[t]&&vis[t]>=i){
a=vis[t]-i;break;
}
}
printf("%lld\n",qpow(B,a));
}
}
```
by 黑客 @ 2020-08-12 21:31:58
@[smarthehe](/user/103732)
by 黑客 @ 2020-08-12 21:32:10
@[黑客](/user/189394) 你的拔山盖世是先枚举大步再枚举小步，而且还是倒着减去次幂，那么你就得把大步尽可能枚举全，覆盖掉 0~p-2 的所有次幂。
你的 $m$ 是 $\lfloor \sqrt{p} \rfloor$，那么实际上必须要到 $m \times (m+2)$ 才能枚举到 $<p-1$ 的所有次幂块，$23$ 就达到了这个上界，其 $m=4$，取 $4 \times 5$ 无法枚举到所有次幂。
by smarthehe @ 2020-08-12 21:46:15
@[smarthehe](/user/103732) 哦，谢谢！
by 黑客 @ 2020-08-12 21:52:13