引入

（北上广深）（拔山盖世）算法，其实是Baby Steps Giant Steps算法
BSGS是大步小步算法的一种，解决ax ≡ b ( mod p) 中非负整数x最小值，其中p为质数。
BSGS算法，原名Baby Steps Giant Steps，又名大小步算法，拔山盖世算法，北上广深算法——by SLYZoier，数论基本算法之一。

问题

题解

讨论

板子

int bsgs(int a,int b,int p)    //BSGS算法
{
    map<int,int> f;
    f.clear();
    int m=ceil(sqrt(p)),now=b;
    for (int j=0;j<=m;j++,now=now*a%p) 
        f[now]=j;
    int powt=qmi(a,m,p);
    now=powt;
    for (int i=1;i<=m;i++,now=now*powt%p)
        if (f.find(now)!=f.end())//这个比下面的查找起来要快 
            return i*m-f[now];
//      if (f[now])              //比较慢，数据范围大时，容易超时。 
//            return i*m-f[now];
    return -1;
}