https://www.luogu.org/problem/P3846
BSGS算法，用于解决求离散对数的问题（拔山盖世（确信））
题目要求$B^L\equiv N (mod p)$
那么我们把形式写成这样：
$B^{im-j}\equiv N (mod p)$
其中$m=\left \lceil \sqrt{p} \right \rceil$
然后显然可以写成
$B^{im}\equiv NB^j (mod p)$
显然i的取值是从1~m的，j的取值是从0~m的
我们将所有$NB^J mod p$的取值算出来，用哈希储存j
然后再枚举im，寻找相等的即可
#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int Q=12255871; struct Hash { int val,id; }h[Q]; int P,B,N,n; int Pow(int x,long long y) {int ans=1;for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ans=1ll*ans*x%P;return ans;} void Insert(int x) { int val=1ll*N*Pow(B,x)%P,i=val%Q; while (h[i].val!=val&&h[i].id>-1) i=(i+1)%Q; h[i].val=val,h[i].id=x; } int Search(long long x) { int val=Pow(B,x),i=val%Q; while (h[i].val!=val&&h[i].id>-1) i=(i+1)%Q; return h[i].id; } int main() { for (int i=0;i<Q;i++) h[i].id=-1; scanf("%d%d%d",&P,&B,&N); if (B%P==0) { printf("no solution"); return 0; } n=sqrt(P);if (n*n!=P) n++; for (int i=0;i<=n;i++) Insert(i); for (long long i=n;i<=P;i+=n) { int j=Search(i); if (j<0) continue; printf("%d",(1ll*i-j+P)%P); return 0; } printf("no solution"); }
原文：https://www.cnblogs.com/mastervan/p/11380830.html
