题解：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 解同余方程即可。

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