只要用欧拉定理递归下去就好了....
然而还是有些细节没考虑好：
$(P,2) \neq 1$时分解$P=2^k*q$的形式，然后变成$2^k(2^{(2^{2^{...}}-k)\ mod\ phi(P)}\ mod\ P)$，不要掉了$-k$
然而取模的时候别乱取模，比如那个$2^k$不应该取模
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; inline int read(){ char c=getchar();int x=0; while(c<‘0‘||c>‘9‘){c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x; } int P; inline int phi(int n){ int m=sqrt(n),re=n; for(int i=2;i<=m;i++) if(n%i==0){ re=re/i*(i-1); while(n%i==0) n/=i; } if(n>1) re=re/n*(n-1); return re; } int Pow(ll a,int b,int P){ ll re=1; for(;b;b>>=1,a=a*a%P) if(b&1) re=re*a%P; return re; } int cal(int x){ if(x==1) return 0; int k=0; while(~x&1) x>>=1,k++; int Phi=phi(x); int re=(cal(Phi)-k%Phi+Phi)%Phi; re=Pow(2,re,x)%x; return re<<k; } int main(){ freopen("in","r",stdin); int T=read(); while(T--){ P=read(); printf("%d\n",cal(P)%P); } }
原文：http://www.cnblogs.com/candy99/p/6424022.html