自动搬运

查看原文

来自洛谷，原作者为

	delta_epsilon 问题在于，大部分以“问题在于”开头的句子，都不是问题。

搬运于2025-08-24 22:57:44，当前版本为作者最后更新于2024-06-02 17:10:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

求 $2^{3^{4^{\cdots^{2023}}}}\bmod2023$ 的值。

解题思路

在小学的时候我们就学过一个求 $a^{b}\bmod k$ 的方法。

也即是将 $a\bmod k,a^2\bmod k,\cdots,a^n\bmod k$ 列出，直到出现了循环，我们就知道答案出来了。

我们可以用如下简单的 Python 程序，快速地求出 $2^i\bmod 2023$ 的周期。

a = 2
cnt = 1
l = []
while not (a % 2023 in l): 
# 只要当前的余数在 l 中没有出现过，就进行循环
    l += [a % 2023] # l 中添加当前余数
    a *= 2          # a <- a * 2
    cnt += 1        # 次数加 1 次
print(cnt)

输出为 $409$，即 $2^{409}\equiv2\pmod{2023}$。

由此可知，$2^i\bmod2023$ 以 $408$ 个为一个周期。

接下来只需要求出指数是一个周期中的第几个即可，也即求 $3^{4^{\cdots^{2023}}}\bmod 408$。

我们将上述 Python 代码中的 2 和 2023 分别改成 3 和 408，可以类似求出 $3^{17}\equiv3\pmod{408}$。

由此可知，$3^{j}\bmod408$ 以 $16$ 个为一个周期。

同理，我们需要求出 $4^{5^{\cdots^{2023}}}\bmod16$ 的值。

显然，因为 $16=4^2$，并且 $5^{6^{\cdots^{2023}}}\gg2$，所以余数为 $0$。

余数为 $0$ 对应着周期的最后一个。也即 $3^{16}\bmod408=273$。

故 $3^{4^{\cdots^{2023}}}\bmod 408=273$。

故 $2^{3^{4^{\cdots^{2023}}}}\equiv2^{273}\pmod{2023}$。

Python 里面用高精度求一下得到结果为 $869$。

提交答案题，直接输出即可。