废话

BSGS 算法，即 Baby Steps Giant Steps，又名大小步算法。
拔山盖世算法、北上广深算法
是一种基础的数论算法

问题

给出 a,b,p 三个整数，其中 p 为素数，求一个未知数 x，使 $a^x \equiv b \mod p$

BSGS

对于上面那个问题，我们可以用 BSGS 解。
怎么解呢？

以下在扯淡：

根据老大爷交换率得出：

没错就是这么简单，化学真奇妙

以上在扯淡：

我们先设 $x=i\times m-j, m=\lceil \sqrt p \rceil$
那么问题就变成了：$a^{i\times m-j} \equiv b \mod p$
即：$a^{i\times m}\div a^j \equiv b \mod p$
即：$a^{i\times m} \equiv a^j\times b \mod p$
那么我们要求的就是 i 和 j 了，使得上面那个式子成立。
显然，当 $i$更小时，$x$会更小，而且小得更快（相对于 j 的变化而言），即 $i$的改变是大步，而 $j$的改变时小步
根据 BSGS，我们先走小步。
从 0~m 枚举 $j$的取值，用哈希表保存 $a^j\times b \mod p$的值
再从 1~m 枚举 $i$的取值，再用 $a^{i\times m}$的值去哈希表里找，如果哈希表里有这个值，那么这对 $i$和 $j$就是我们要求的了。
而答案就是 $i\times m-j$
这样做的复杂度是 $O(\sqrt p)$的！

一些讨论

1. 无解：始终哈希表内没有找到存在的值，无解
2. 为什么 $m$的取值是 $\lceil \sqrt p \rceil$？因为这样能覆盖到所有可能值
3. 为什么 $i$不能取 0？因为如果 $i$等于 0 可能出现解为负数
4. 为什么先小步再大步得到的解就是最小的解？因为对 $x$的大小影响较大的是 $i$，$i$每次加 1，$x$都会增加 m，而 $j$的取值范围是 0 到 $m$，不会超过 $i$每次+1 的增幅，所以当 $i$最小时，答案一定最小

例题

POJ – 2417 Discrete Logging
传送门=￣ω￣=

模板题
但是这题貌似。。。用 map 容易挂，用 map 的 count 函数会超时。。。所以我手动给 j 上 1 再放哈希表里，使用时再减回来，这样就能用 [] 运算符了（更快些）。
数据貌似。。。很水，你枚举 j 从 1 开始也行

代码（目前 vjudge 最短）：

#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
LL a,b,c,m,tot,am;
map<LL,int> h;
int main()
{
    while(~scanf("%lld%lld%lld",&c,&a,&b))
    {
        m=ceil(sqrt(c)),tot=1,h.clear();
        for(int i=0;i<=m;i++)h[tot*b%c]=i+1,am=tot,tot=tot*a%c;
        tot=am;
        for(int i=1;i<=m;i++,tot=tot*am%c)
            if(h[tot])
            {
                printf("%lld\n",i*m-h[tot]+1);
                goto end;
            }
        printf("no solution\n");
        end:;
    }
    return 0;
}