求 \(\huge2^{2^{2^{2^{....}}}} mod_p\)
递归使用欧拉定理求解即可
#include #include #include #include #include #include #include #include #include #include #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const ll mxn=1e7+5; ll tot,n,m,mod,cnt; inline ll read() { char c=getchar(); ll x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(ll &x,ll y) {if(xy) x=y;} int vis[mxn+5],p[1000000],ph[mxn+5]; ll qpow(ll a,ll b,ll p) { ll res=1,bs=a; while(b) { if(b&1) res=1ll*res*bs%p; bs=1ll*bs*bs%p; b>>=1; } return res; } void sieve() { vis[1]=ph[1]=1; for(ll i=2;i<=mxn;++i) { if(!vis[i]) ph[i]=i-1,p[++tot]=i; for(ll j=1;j<=tot&&i*p[j]<=mxn;++j) { vis[p[j]*i]=1; if(i%p[j]==0) { ph[p[j]*i]=p[j]*ph[i]; break; } else ph[p[j]*i]=ph[p[j]]*ph[i]; } } } ll solve(ll x) { if(x==1) return 0; return qpow(2,solve(ph[x])+ph[x],x); } int main() { ll T; T=read(); sieve(); while(T--) { mod=read(); printf("%lld\n",solve(mod)); } return 0; }