bzoj千题计划264：bzoj3884: 上帝与集合的正确用法

http://www.lydsy.com/JudgeOnline/problem.php?id=3884

欧拉降幂公式

 

#include<cmath>
#include<cstdio>

using namespace std;

int get_phi(int p)
{
    int phi=p;
    int m=sqrt(p);
    for(int i=2;i<=m;++i)
        if(p%i==0)
        {
            phi=phi/i*(i-1);
            while(p%i==0) p/=i;
        }
    if(p>1) phi=phi/p*(p-1);
    return phi;
}

int Pow(int a,int b,int p)
{
    int res=1;
    for(;b;a=1LL*a*a%p,b>>=1)
        if(b&1) res=1LL*res*a%p;
    return res;
}

int f(int p)
{
    if(p==1) return 0;
    int phi=get_phi(p);
    return Pow(2,f(phi)+phi,p);
}

int main()
{
    int T,P;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&P);
        printf("%d
",f(P));
    }
}