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

· · 题解

  • 本题解于 2024 年 05 月 30 日彻底重构，点击查看原题解备份。

    关于原题解的一些话：评论区有同学反应做法存在缺陷或错误，本人已经搬运所有评论至备份区。希望有数论大佬可以和我讨论一下原题解的正确性或对于本题结果正确的原因。拜谢并对被我误导的同学诚恳道歉！

前置知识：拓展欧拉定理，建议先做模板题。

本题要求 2^{(3^{(4^{(\ldots ^{2023})})})}\bmod\;2023。

优先考虑费马小定理，但是很可惜的是，2023=7\times289，因此不是质数，无法采用费马小定理。

考虑欧拉定理，欧拉定理要求 \gcd\left(a,p\right)=1,a,p\in\N^*（其中，a=2 为底数、p=2023 为模数）。底数为 2 时欧拉定理显然成立，但是当底数为 3 时 \gcd\left(3,\varphi(2023)\right)\neq1， 所以欧拉定理应当是错误的。但是对于本题而言答案正确，有知道原因的朋友欢迎私信讨论 。

考虑拓展欧拉定理，当 a,b,p\in\Z 时有 a^b\equiv\ \begin{cases} a^b &\text{if}& b<\varphi(p) \\ a^{b\bmod\varphi(p)+\varphi(p)} &\text{if}& b\ge \varphi(p) \end{cases}(\bmod\;p)。网上证明较多，这里暂且省略。

计算 2^{(3^{(4^{(\ldots ^{2023})})})}\bmod 2023 时展开即可，注意展开时每个指数的模数并不相同。

算出答案为 869，代码如下：

#include<bits/stdc++.h>
using namespace std;
const int n=2023,mod=2023;
inline int get_eular(int n){
    int ret=n;
    for(int i=2;i<=n/i;i++)if(n%i==0){
        while(n%i==0)n/=i;
        ret=ret/i*(i-1);
    }
    if(n>1)ret=ret/n*(n-1);
    return ret;
}
inline int quick_pow(const int a,const int b,const int mod){
    if(!b)return 1;
    const int ret=quick_pow(a,b/2,mod);
    return ret*ret%mod*(b%2?a:1)%mod;
}
inline int get_ans(const int a,const int mod){
    if(a==n)return a;
    return quick_pow(a,get_ans(a+1,get_eular(mod))+get_eular(mod),mod);
}//由于代码是重构而来，作者偷懒并没有重写欧拉函数相关代码。求欧拉函数可以先预处理以加快代码运行速度
signed main(){
    cout<<get_ans(2,mod); 
}

最后放个小花絮：点击这里查看。