我们知道这题的 $\text{BSGS}$ 是这样的：

设 $l=A \lceil \sqrt{p} \rceil-B$，其中 $0\le A,B \le \lceil \sqrt{p} \rceil$。带入原同余方程得到

$b^{A \lceil \sqrt{p} \rceil}\equiv n\times b^{B}\pmod p$

然后可以暴力枚举 $A,B$ 计算左右两边 模 $p$ 意义下的值看是否出现匹配。

我的问题：

我代码的写法是找到一个 $(n\times b^{B})\bmod p$ 的值就将 $\text{unordered\_map}$ 中 $(n\times b^{B})\bmod p$ 下标处的值标记为 $B$，方便后面计算答案。如下：

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
int inv=1,p,b,n;
unordered_map<int,int> m;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>p>>b>>n;
    int SQRT=ceil(sqrt(p));
    for(int B=0;B<=SQRT;B++){
        int now=n*inv%p;
        if(m[now]){
            cout<<"错误";
            return 0;
        }
        m[now]=B;
        inv=(inv*b)%p;
    }
    inv=1;
    int ans=inf,temp=1;
    for(int i=1;i<=SQRT;i++)temp=temp*b%p;
    for(int A=0;A<=SQRT;A++){
        int now=inv;
        if(m[now]&&A*SQRT-m[now]>=0)ans=min(ans,A*SQRT-m[now]);
        inv=(inv*temp)%p;
    }
    if(ans!=inf)cout<<ans;
    else cout<<"no solution";
    return 0;
}

但是容易发现如果存在两个不同的 $0\le i,j \le \lceil \sqrt{m} \rceil$ 满足 $nb^i\equiv nb^j \pmod p$ 的时候这个将会少算其中一个对答案的贡献，但是我的代码过了，于是我尝试证明在这个数据范围内 $nb^i\equiv nb^j \pmod p$ 不可能成立，但是却发现它是可以成立的。

给出一组使其成立的数据：$n=2,b=2,p=15,i=4,j=0$

然后通过特判

for(int B=0;B<=SQRT;B++){
      int now=n*inv%p;
      if(m[now]){
          cout<<"错误";
          return 0;
      }
      m[now]=B;
      inv=(inv*b)%p;
  }

发现数据里面并没有这种情况，所以

1.可以帮我解释一下为什么这个过了吗？

2.如果是数据问题需要修复数据吗？