【备份，可能有误】题解：P10414 [蓝桥杯 2023 国 A] 2023 次方

· · 题解

  • 本题解于 2024 年 05 月 30 日彻底重构，这里是原题解的备份（可能有误），点击查看最新题解。

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

前置知识：欧拉定理。

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

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

考虑欧拉定理，a^{\phi\left(p\right)}\equiv1\left(\bmod\;p\right),\gcd\left(a,p\right)=1。
令 b=c\phi\left(p\right)+d，则 a^b=a^{c\phi\left(p\right)+d}\equiv a^d=a^{b\bmod \phi\left(p\right)}\left(\bmod\;p\right)。幸运的是，\gcd\left(2^i,2023\right)=1,i\in\N^*，所以可以采用欧拉定理。

计算 2^{(3^{(4^{(\ldots ^{2023})})})}\bmod 2023 时每次做幂运算时把指数替换成指数对 \phi\left(2023\right) 取模的值即可。

计算 \phi\left(2023\right) 的过程不做过多赘述，如果不会的话请自行寻找教程。

本题最终答案为：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;
}
signed main(){
    const int a=get_eular(mod);
    int ans=n;
    for(int i=n-1;i>=3;i--)ans=quick_pow(i,ans,a);
    cout<<(ans=quick_pow(2,ans,mod));
}