bzoj3884 上帝与集合的正确用法

根据扩展的欧拉定理，有
222⋯%p=2(22⋯%φ(p)+φ(p))%p
指数上带无穷的部分变成了一个子问题，递归求解。当 p=1 时，显然答案为 0 。复杂度 O(Tlogpp√) 。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long
int pow(int k,int p)
{
int base=2,ret=1;
for (;k;k>>=1,base=(LL)base*base%p)
if (k&1) ret=(LL)ret*base%p;
return ret;
}
int solve(int p)
{
if (p==1) return 0;
int m=sqrt(p+0.5),x=p,phi=p;
for (int i=2;i<=m;i++)
if (x%i==0)
        {
            phi=phi/i*(i-1);
while (x%i==0) x/=i;
        }
if (x>1) phi=phi/x*(x-1);
return pow(solve(phi)+phi,p);
}
int main()
{
int p,T;
scanf("%d",&T);
while (T--)
    {
scanf("%d",&p);
printf("%d\n",solve(p));
    }
}