Exponial Gym - 101550E (欧拉降幂) 2019-10-09 杂项 暂无评论 65 次阅读 ## 题目链接：[https://codeforces.com/gym/101550/attachments](https://codeforces.com/gym/101550/attachments) ## 题意： 设函数 exponial(n) = $n^{(n-1)^{(n-2)^{...^{2^{1}}}}}$，求exponial(n) mod m的值。 ## 思路 欧拉降幂： 利用欧拉降幂公式$a^{b}$% p = $a^{ b \% \varphi( p)+ \varphi( p)}$% p$,b\geqslant \varphi (p)$ 可得到递推公式: exponial(n) mod m=n^(exponial(n-1) mod φ(m)+φ(m)) mod m 注： (1) 当模数为1的时候应直接返回0 (2)因为b < $\varphi(p)$ 时，降幂公式失效； n=1,2,3,4 时，exponial(n)不一定>=m, 所以不能直接用公式， 可以直接暴力； 当n >=5 ,exponial(n)>1e18， 这样就一定能确保exponial(n)>p; 可以直接用公式； 由于运算过程中不断地对m取它的φ值，下降速度是很快的，所以不用担心递归层数过多。 ## 代码 ```javascript #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,PHI; ll phi(ll x) { ll ret=x; for(ll i=2;i*i<=x;++i) { if(x%i==0)ret=ret/i*(i-1); while(x%i==0)x/=i; } if(x>1)ret=ret/x*(x-1); return ret; } ll Pow(ll x,ll p,ll mod) { ll ret=1; while(p) { if(p&1)ret=ret*x%mod; x=x*x%mod; p>>=1; } return ret; } ll euler_pow(ll x,ll mod) { if(mod==1)return 0; if(x==1)return 1%mod; if(x==2)return 2%mod; if(x==3)return 9%mod; if(x==4)return (1ll<<18)%mod; ll PHI=phi(mod); return Pow(x,euler_pow(x-1,PHI)+PHI,mod); } int main() { scanf("%lld%lld",&n,&m); printf("%lld\n",euler_pow(n,m)); return 0; } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭