题解：P12239 [蓝桥杯 2023 国 Java A] 游戏的得分

感谢 diqiuyi 提供了一种更快的做法，前置芝士：十四字算法。

这道题相当于要询问多组模同一个数的 BSGS，因此想到 基于值域预处理的快速离散对数，它可以 $O(\log p)$ 快速回答 BSGS，代价是一次 $O(p^{\frac{3}{4}}/\log^{0.5}p)$ 的预处理，对于这道题来说完美适配。

但是，它由于使用了 $\log$ 的性质，所以只能对于原根求出离散对数，无法在此题直接应用。

因此，我们先预处理出 $A=\log_3 2$。

每次询问时，记询问的数是 $x$，我们求出 $B=\log_3x$，由换底公式，我们有 $\log_2 x=\frac{\log_3 x}{\log_3 2}$。

但由于在指数上，模数非质数的缘故，我们无法直接求出 $\log_3 2$ 的逆元，但是我们可以退而求其次：

容易发现，当且仅当方程 $xA\equiv B(\bmod\ p-1)$ 有解时，$x$ 的最小非负整数解刚好满足换底公式（否则，可以证明原方程必然无解），$x$ 即所求，因此再写一个 exgcd 解同余方程即可。

轻松抢下目前最优解，提交记录。