问题
给出(a,b,p)，求最小的(x)使得(a^xequiv bmod p)。
BSGS算法
Baby-Steps-Giant-Steps算法可以在(sqrt p)的时间内求解这个问题，它利用了两个不同步长的遍历。
[egin{aligned}
令m&=sqrt p \
a^{im-j}&equiv b mod p \
a^{im}&equiv ba^j, iin[1,m],jin[0,m]
end{aligned}
]
首先求出所有(ba^j,jin[0,m])，存入哈希表中。若哈希表中已有相同的(ba^j)，那么我们更新到(j)比较大的那个。再从小到大枚举(i)，在哈希表中查询(a^{im})是否存在即可。由于我们要令(x)最小，而(x=im-j)，所以要令(j)最大，(i)最小。
这个算法是成立的，原因是，对于朴素的枚举，我们枚举(xin [0,p-1])即可，而这个算法利用了中途相遇的思想，相当于是枚举了这些值。
离散对数是一个重要的工具，在求解模意义下的方程中很有用。
代码
#include<cstdio>
#include<cctype>
#include<map>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long giant;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int q=1e9+7;
int mi(int x,int y) {
int ret=1;
for (;y;y>>=1,x=(giant)x*x%q) if (y&1) ret=(giant)ret*x%q;
return ret;
}
const int maxn=1e5+7;
const int maxm=1e7+1;
struct node {
int val,x,nxt;
};
struct HASH {
int h[maxn],tot;
node e[maxm];
void init() {
memset(h,0,sizeof h);
tot=0;
}
void insert(int v,int j) {
int t=v%maxn;
for (int i=h[t];i;i=e[i].nxt) if (e[i].val==v) {
e[i].val=v;
e[i].x=j;
return;
}
e[++tot]=(node){v,j,h[t]};
h[t]=tot;
}
int find(int x) {
int t=x%maxn;
for (int i=h[t];i;i=e[i].nxt) if (e[i].val==x) return e[i].x;
return -1;
}
} has;
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
int m=(int)sqrt(q)+1;
int T=read();
while (T--) {
int a=read(),b=read();
int am=mi(a,m);
has.init();
for (int j=0,tmp=b;j<=m;++j,tmp=(giant)tmp*a%q) {
has.insert(tmp,j);
}
int x=-1;
for (int i=1,tmp=am;i<=m;++i,tmp=(giant)tmp*am%q) {
int y=has.find(tmp);
if (~y) {
x=i*m-y;
break;
}
}
printf("%d
",x);
}
return 0;
}