【Python党福利】题解：P10414 [蓝桥杯 2023 国 A] 2023 次方

· · 题解

原题解在过审后又被撤下了，默哀（（（

好，那我就好好研究欧拉定理，正确解出这道题！

思路

前置知识：欧拉定理 Link，附上自己写的解析QwQ。

根据欧拉定理可得：

a^{\phi(n)} \equiv 1 \pmod n,\gcd(a,n) = 1

设一数 b=n1\phi(n)+n2，那么 a^{b} \equiv a^{n2}\pmod n。 所以 a^{b} \equiv a^{b \bmod \phi(n)}\pmod n。

p.s.以上感谢@2011FYCCCTA 线下讲解。

所以就可以在某些情况下让指数对 2023 取模，从而缩减时间复杂度。

因为 2 与 2023 互质，所以 第一层 可以使用欧拉定理。

但是往上推的话就不好说了，需要挨个处理。

Code

# 欧拉函数
def eular(n):
    phi = n
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
            continue
        while n % i == 0:
            n //= i
        phi = phi // i * (i - 1)
    if n > 1:
        phi = phi // n * (n - 1)
    return phi

# 快速幂
def quick(base, x, mod):
    res = 1
    while x:
        if x & 1:
            res = res * base % mod
        base = base * base % mod
        x >>= 1
    return res

a = eular(2023)
t = 2023
for i in range(2022, 2, -1):
    t = quick(i, t, a)
t = quick(2, t, 2023)
print(t)

记录

AC