```cpp
int BSGS(int a, int b, int p){
int t = sqrt(p) + 1; b %= p;
map<int, int> hash; hash[b] = 0;
for(int i = 1; i <= t; i++) //x的等指这里
b = 1ll * b * a % p, hash[b] = i;
int s1 = qpow(a, t, p), s2 = s1;
for(int i = 1; i <= t; i++){ //y的等指这里
auto iter = hash.find(s2);
if(iter != hash.end()) return i * t - iter -> second;
s2 = 1ll * s1 * s2 % p;
}
return -1;
}
```
by Missa @ 2022-04-03 12:51:34
今天发现我同学把 `t=sqrt(p)` 写成了 `t=sqrt(n)` 都过了。
这数据该有多水啊……
by Missa @ 2022-04-04 17:27:10
@[Missa](/user/443664)
$2\le b$
by fast_proton @ 2022-08-16 09:39:30