题解：P10414 [蓝桥杯 2023 国 A] 2023 次方

· · 题解

题目大意

求 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。

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