感觉是今天洛谷月赛T3的弱化版，会写洛谷T3之后这题一眼就会写了...
还是欧拉扩展定理
于是就在指数上递归%phi(p)+phi(p)直到1，则后面的指数就都没用了，这时候返回，边回溯边快速幂。因为一个数最多求log次phi就变成1，所以复杂度为O(logp*sqrt(p))，这题线性筛是比直接求要慢的...
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=1010,inf=1e9; int T,x; int p[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } inline int phi(int x) { int ans=x; for(int i=2;i*i<=x;i++) if(!(x%i)) { ans=ans/i*(i-1); while(!(x%i))x/=i; } if(x>1)ans=ans/x*(x-1); return ans; } inline int power(int a,int b,int mod) { if(!a)return 0;int ans=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b&1)ans=1ll*ans*a%mod; return ans; } int solve(int mod) { if(mod==1)return 0;int tmp; return power(2,solve(tmp=phi(mod))+tmp,mod); } int main() { read(T); while(T--)read(x),printf("%d ",solve(x)); return 0; }