介绍一种升级版的 BSGS 科技，若在模 \(P=p_1^{e_1}\cdots p_k^{e_K}+1\) 意义下求离散对数，可以做到 \(O(\sum \sqrt{p_i^{e_i}})\) 以及 \(O(\sum e_i\sqrt {p_i})\) 的复杂度。
先看怎么做前者。
考虑怎么求出 \(n\) 模 \(p_i^{e_i}\) 的值。有 \((a^{(P-1)/p_i^{e_i}})^n=(a^n)^{(P-1)/p_i^{e_i}}=b^{(P-1)/p_i^{e_i}}\pmod P\)。
所以可以令 \(a'=a^{(P-1)/p_i^{e_i}},b'=b^{(P-1)/p_i^{e_i}}\) 然后求出对应的 \(n'\)，因为 \((a')^n\) 的循环长度是 \(p_i^{e_i}\)，所以用 BSGS 求 \(n'\) 是 \(O(\sqrt{p_i^{e_i}})\) 的。而 \(n\bmod {p_i^{e_i}}=n'\)，所以拿这些 \(n'\) 做 CRT 合并起来即可。如果 CRT 无解就是原来的 \(n\) 无解。
复杂度 \(O(\sum \sqrt{p_i^{e_i}})\)。
再看看怎么做后者。延续上面的做法，要求 \(n'\) 使得 \((a^{(P-1)/p_i^{e_i}})^{n'}=b^{(P-1)/p_i^{e_i}}\pmod P\).
因为 \(n'\) 到了 \(p_i^{e_i}\) 就循环，可以认为 \(n'<p_i^{e_i}\)，因此把 \(n'\) 写成 \(p_i\) 进制的形式只有 \(e_i\) 位：记作 \((d_{e_i-1}d_{e_i-2}\dots d_0)_{p_i}\)，其中 \(d_j\) 对应 \(p_i^j\) 的位。
求 \(n'\) 就是求 \(d_0\sim d_{e_i-1}\)，考虑从前往后求。设当前求出了 \(d_0\sim d_{pos-1}\) 怎么求出 \(d_{pos}\)。
记 \(N=(d_{pos-1}\dots d_0)_{p_i}\)，那么 \(n'=N+d_{pos}p_i^{pos}+d_{pos+1}p_i^{pos+1}+\cdots\)，写下来：
然后两边同时 \(\frac{P-1}{p_i^{pos+1}}\) 次方，那么 \(pos+1\) 往后的项因为 \(P-1\mid p_i^{pos+k}\frac{P-1}{p_i^{pos+1}}\) 所以全部变成 \(0\) 了，于是：
再同时乘以 \((a')^{N\frac{P-1}{p_i^{pos+1}}}\) 模 \(P\) 的逆元（快速幂即可），右边会得到一坨常数记作 \(C\)：
那么我们发现 \(d_{pos}\) 会在 \(p_i\) 处就循环，所以上 BSGS 可以在 \(O(\sqrt{p_i})\) 的时间内求出 \(d_{pos}\)。
因此总复杂度是 \(O(\sum e_i\sqrt{p_i})\) 的。
例题：CF1310F
题意为 Nimber 域上的离散对数。因为我不会 nimber，所以假设乘法是 \(O(1)\) 的。那么直接套上面的算法即可。