P12540 题解 / [XJTUPC 2025] O

ztd___ · 2025-05-19 12:52:31 · 题解

观察到了指数、模意义，素数二字也加粗了，考虑费马小定理：a ^ {p - 1} \equiv 1 \pmod{p}。其中 p 为任意素数。

做一做会发现极难构造与 a 和 c 有关的 b。于是我们大胆猜测 a，c 与 b 之间没有任何关系。

结合费马小定理不难猜测出来，式子的左边极有可能是 1。这就意味着 a^b 是若干个 1（即 a ^ {p - 1}）的乘积。此时由幂的计算规律不难知道，b 一定是若干个 p - 1 的和。

不妨设 b = k \times (p - 1)。

这样式子左边是 1，意味着右边也是 1。

容易发现 p - 1 \equiv -1 \pmod{p}，所以 b \equiv -1 \times k \pmod{p}。

所以右边就是 (-1 \times k)^c。

因为右边是 1，所以我们大胆猜测底数（即 -1 \times k）就是 1。这样就可以计算出 k = -1。

而 b 不能是负数，所以把 k 转化为 p - 1 即可。

答案就是 (p - 1)^2。

另一种思考方法。

注意到去年的最后一题也是答案极其简单的数学题，不妨猜测今年的答案也会异常简单。

发现 p 是素数被加粗了，所以答案肯定和 p 有密切的关系。

大胆猜测答案不会很离谱。

对 p，p + 1，p - 1，p^2，p^2 - 1，p^2 + 1，(p + 1)^2，(p - 1)^2 等等近似的 b 进行枚举，就可以发现 (p - 1)^2 就是答案。