我放弃挣扎了
至少除了这个点，我的 BSGS exBSGS 都是可以过的，我就姑且当它没有问题了！
BSGS : Big Step Giant Step
额其实我也不懂这个算法和名字有什么关系，倒是有点根号分治的味道~
这个东西用来求解一个东西 \(x\) 使得：
\[a^x \equiv b \pmod p \]其中 \(a,b,p\) 给定且 \(p\) 为质数
接下来直接上操作：
令 $$t = \left \lceil \sqrt{p}\right \rceil $$
令 $$x = i \times t - B$$ 那么由于 \(p\) 是质数所以我们可以进行一番操作将原式变形为 $$a^{i\times t - B} \equiv b \pmod p$$
进一步得到
\[a^{i\times t} \equiv b^B \pmod p \]注意！！！
这一步是进行了除法，必须保证逆元存在，而这等价于 \(a^B,p\) 互质，进而等价于 \(a,p\) 互质，所以其实只要求 \(a,p\) 互质即可！！
然后发现这里的 \(i \in [1,t] , B \in [0,t]\) 所以这两个东东都是 \(\sqrt{p}\) 级别的。那么考虑将右边的 \(b^B\) 插入哈希表记录对应的 \(B\) ，然后 \(O(\sqrt{p})\) 枚举左边的 \(a^{i\times t}\) 查询对应的哈希表即可。然后注意特判 \(i \times t - B \ge 0\) 即可
unordered_map<int,int>mp;
int BSGS(int a,int b,int p){
mp.clear();
int t = ceil(sqrt(p)),res = b;
rep(i,0,t){
mp[res] = i;
res = 1ll * res * a % p;
}
int base = ksm(a,t,p);res = base;
if(a == 0)return b == 0 ? 1 : -1;
rep(i,1,t){
if(mp.count(res)){
//其实这样常数飞快，但是好像就是这种不用快速幂的方法导致了 wa
//改了就变成TLE了，所以可以自行更改
if(i * t - mp[res] >= 0)return i * t - mp[res];
}
res = 1ll * res * base % p;
}
return -1;
}
exBSGS
这里其实就是把 \(p\) 扩展到任意数了。
那么这里的 \(a,p\) 不互质了，我们考虑把他变成互质的不就好了！
重新观察式子
\[a^{x} \equiv b \pmod p \]首先令 \(g = \gcd (a,p)\)
方程可以变为
\[\frac{a}{g} \times a^{x-1} \equiv \frac{b}{g} \pmod {\frac{p}{g}} \]无解情况的话就是 \(g \nmid b\) 且 \(b \ne 1\) 因为 \(b = 1\) 直接 \(x = 0\) 就好了，别的手推下不定方程很好证明。
于是我们可以重复这个过程,直至 \(\gcd (a,p) = 1\) 并且得到了 \(k\) 个 \(g\)
令 $u = {\textstyle \prod_{i=1}^{k}} \frac{a}{g_{i}} ,v = \textstyle \prod_{i=1}^{k}g_{i} $你会发现每个 \(\frac {a}{g_{i}}\) 都与现在的 \(\frac{p}{v}\) 互质，因为 \(\frac{p}{v}\) 现在与 \(a\) 互质，自然与 \(\frac{a}{g_{i}}\) 互质，所以 \(u\) 与 \(p\) 互质，所以存在逆元。
\[a^{x-k} \times u \equiv \frac{b}{v } \pmod {\frac{p}{v}} \]\[a^{x-k} \equiv \frac{b}{uv} \pmod {\frac{p}{v}} \]所以算一下 \(u\) 的逆元，这个就变成了普通的 BSGS 辣！
void exgcd(int a,int b,int &d,int &x,int &y){
if(!b){
d = a;x = 1;y = 0;return;
}
exgcd(b,a%b,d,y,x);
y -= x * (a / b);
}
inline int inv(int a,int p){
int d,x,y;
exgcd(a,p,d,x,y);
return (x % p + p) % p;
}
int exBSGS(int a,int b,int p){
if(b == 1 || p == 1)return 0;
int g = __gcd(a,p),k = 0,mul = 1;
while(g > 1){
if(b % g)return -1;
++k;b /= g;p /= g;
mul = mul * (a / g) % p;
if(mul == b)return k;
g = __gcd(a,p);
}
int x = BSGS(a,b * inv(mul,p) % p,p);
if(x == -1)return x;
return x + k;
}