【Bzoj3884】上帝与集合的正确用法

题目大意

求2222222...mod　p的值。

分析

po姐的题目诶！！
大意就是上面那样，看上去+∞个2根本不可做，不过有欧拉定理xa≡xa　mod　φ(p)+φ(p)　(mod　p)。
那么我们有f(n)=2222222...(mod　n)
=2(222222...　mod　φ(n))+φ(n)　(mod　n)
=2f(φ(n))+φ(n)　(mod　n)
递归做下去即可，当n==1，返回0(任何数mod　1等于0)。
欧拉函数建议直接算，递推不知道会不会TLE。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

int t;
LL x;

LL phi(LL n){
    LL tmp = n;
for(LL i=2;i*i<=n;i++)
if(n%i == 0){
            tmp = tmp/i*(i-1);
while(n%i == 0) n /= i;
        }
if(n > 1) tmp = tmp/n*(n-1);
return tmp;
}

LL pwr(LL n,LL k,LL p){
    LL ans = 1;
while(k) {if(k&1) ans=(ans*n)%p;n=(n*n)%p;k>>=1;}
return ans;
}

LL f(LL p)  
{  
if(p==1) return 0;
    LL phi_p=phi(p);
return pwr(2,f(phi_p)+phi_p,p);
}

int main(){
scanf("%d",&t);
while( t-- ){
scanf("%lld",&x);
printf("%lld\n",f(x));
    }
return 0;
}