刚开始我想的是欧拉降幂，可是觉得复杂度还是挺高的就去找了一下题解。
思路大方向没有问题，仍然是使用欧拉函数降低指数然后递归处理。但是不是简单的使用欧拉降幂而是应该对模数p稍微处理一下。因为底数已经确定为2，所以我们可以将p写成p=2k*q，q为奇数的形式，则
22的无穷次方%p=2k(22的无穷次方-k%q)
这样可以直接对新的指数直接模q的欧拉函数值进行处理，因为每次q为奇数，q的欧拉函数值一定为偶数（他的因子一定是奇素数，奇素数的欧拉函数值一定是偶数），所以每次至少将p变为原来的一半，所以复杂度比较低。因为用到的欧拉函数值不是很多，所以直接求单点的欧拉函数值即可。
需要注意的是指数-k模欧拉函数值时应该保证指数大于0
AC代码
#include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cmath> #include<cstdlib> #include<ctime> #include<map> #include<queue> #include<set> #include<vector> using namespace std; typedef long long ll; const int MAXN=1e5+5; ll p; ll quick_pow(ll a,ll b,ll p) { a%=p; ll ret=1; while(b) { if(b&1) ret=ret*a%p; a=a*a%p; b>>=1; } return ret; } ll quick_pow(ll a,ll b) { ll ret=1; while(b) { if(b&1) ret*=a; a*=a; b>>=1; } return ret; } ll phi(int x) { ll ret=x; for(int i=2;i*i<=x;i++) { if(x%i==0) { ret=ret-ret/i; while(x%i==0) x/=i; } if(x==1) break; } if(x>1) ret=ret-ret/x; return ret; } ll deal(ll p) { ll k=0; while(~p&1) k++,p>>=1; if(p==1) return 0; ll phip=phi(p); return quick_pow(2,(deal(phip)-k%phip+phip)%phip,p)<<k; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%lld",&p); printf("%lld\n",deal(p)); } return 0; }