BSGS
BSGS可以用于解决一类离散对数问题，一般形如
[A^xequiv Bpmod C
]
其中(C)为质数
它是怎么做的？
我们令(m=lceilsqrt{C} ceil)，那么(x=im+j,iin[0,m-1],jin[0,m-1])
于是原方程转化为
[A^{im} imes A^jequiv Bpmod C
]
即
[A^jequiv B imes A^{-im}pmod C
]
我们知道(gcd(A,C)=1)，所以(A)在模(C)意义下存在逆元，(A^k)也是
那么我们将所有的(A^j)存进哈希表里((Babyspace Step))，然后枚举(i(Giantspace Step))，如果找到一个(i)满足上式，那么我们就找到了一个解(x=i imes m+j)
如果(i)在([0,m-1])内没有解，那么原方程无解
因为根据欧拉定理，(A^{varphi(C)}=A^{C-1}equiv1pmod C,A^Cequiv Apmod C)，出现循环节
所以原方程如果有解，最小的解一定在([0,C-1])范围内，否则无解
时间复杂度(O(sqrt{C}))
但是我太菜了，不会写哈希表，只会用(map)，时间复杂度到了(O(sqrt Clogsqrt C))，才能勉强维持一下生活这样子
BSGS是一种典型的空间换时间的思想
例题
板题，直接上BSGS就可以了
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#define mp(x,y) (make_pair((x),(y)))
#define inv(x) (fastpow((x),c-2))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
template <typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=c=='-';c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
ll a,b,c;
ll m;
map<ll,ll> rec;
ll fastpow(ll a,ll b)
{
ll re=1,base=a;
while(b)
{
if(b&1)
re=re*base%c;
base=base*base%c;
b>>=1;
}
return re;
}
int main()
{
read(c),read(a),read(b);
rec.clear();
m=ceil(sqrt(c));
for(register ll i=0,po=1;i<m;++i,po=po*a%c)
rec.insert(mp(po,i));
ll iam=inv(fastpow(a,m));
for(register ll i=0,tmp=1;i<m;++i,tmp=tmp*iam%c)
if(rec.find(b*tmp%c)!=rec.end())
{
printf("%lld
",m*i+rec[b*tmp%c]);
return;
}
printf("no solution
");
return 0;
}