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

_Sky_Dream_ · 2024-05-06 05:07:32 · 题解

传送门

首先，快速幂了解一下，知道他快速就好（膜拜巨佬）。

首先可以采用暴力的思想，在计算指数的时候取模。

a 很好，有思路是不错的，但想法是错的！对于幂来说，指数是不可以随便取模的！

再深一层，来看看费马小定理：

令 b=cϕ(n)+d，则有 a^b≡a^{cϕ(n)+d}≡ a^d(mod\hspace{1mm}n)。

所以 a^b≡ a ^{b\hspace{1mm}mod\hspace{1mm}ϕ(n)}(mod\hspace{1mm}n)。

用欧拉定理可以省去一些指数。

AC Code

//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define itn int
#define tni int
#define tin int
#define nit int
#define nti int
#define int long long
#define MAX 1145141919810
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rp(i,x,y) for(int i=x;i>=y;--i) 
using namespace std;
int jyaakioi(int n){//欧拉定理
    int jya=n;
    rep(i,2,n/i){
        if(n%i)continue;
        while(n%i==0)n/=i;
        jya=jya/i*(i-1);
    }
    if(n>1)jya=jya/n*(n-1);
    return jya;
} 
int Manba_Out(int jyt,int x,int ysc){//快速幂
    int txy=1;
    while(x){
        if(x&1)txy=txy*jyt%ysc;
        jyt=jyt*jyt%ysc;
        x>>=1;
    }
    return txy;
} 
void Enchanted(){
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int a=jyaakioi(2023); 
    int t=2023; 
    rp(i,2022,3)t=Manba_Out(i,t,a);
    cout<<Manba_Out(2,t,2023);
    exit(0);
}
signed main(){Enchanted();}

好奇特的变量。