P184's Solution

在原版做法的基础上，我们通过打表（或者查 [OEIS A049048](https://oeis.org/A049048)）可以发现，对应答案不为 $1$ 的合数只有 $2107$ 个。于是我们可以先用 Miller-Rabin（选取 $2,7,61$ 为底数判断三次）做素性判断，再对合数查表（查不到说明答案为 $1$）。该做法的时间复杂度为 $O(T \log n)$。

• 217 次浏览
• 2025-9-4 22:00:08