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 
      
        #include 
       
        #include 
        
         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