大家好，又见面了，我是全栈君。
题意：要你算这个玩意额：\(2^{2^{2^{…}}}\)
题解：
欧拉定理+递归
设\(p=2^k*q （q为奇数）\)
题目要求\(2^{2^{2^{…}}}modp\)
变形为\(2^k（2^{2^{2^{…}}-k}modq）\) （这里需要在草稿纸上算一下）
由于q是个奇数，那么肯定与2的指数互质
原式变为\(2^k(2^{(2^{2^{…}}-k)mod\phi(q)}modq)\)
然后就可以递归求解了，当模数为1的时候，递归就结束了，然后就可以回溯计算了
递归次数不超过\(log_2p\) ,单次求\(\phi(p)\)的复杂度为\(\sqrt{p}\)
所以总复杂度为\(T*log_2p*\sqrt{p}\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
int gi() {
int x=0,o=1; char ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') o=-1,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return o*x;
}
int get_phi(int x) {
int ret=x;
for(int 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;
}
int qpow(ll x, int y, int mo) {
ll ret=1;
while(y) {
if(y&1) ret=ret*x%mo;
x=x*x%mo,y>>=1;
}
return ret;
}
int solve(int p) {
if(p==1) return 0;
int k=0,phi,ret;
while(!(p&1)) p>>=1,k++;//while(p是个偶数)
phi=get_phi(p);
ret=solve(phi);
(ret+=phi-k%phi)%=phi;
ret=qpow(2,ret,p)%p;
return ret<<k;
}
int main() {
int T=gi();
while(T--) {
int p=gi();
printf("%d\n", solve(p));
}
return 0;
}转载于:https://www.cnblogs.com/HLXZZ/p/7617318.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108127.html原文链接：https://javaforall.net
