bzoj3884

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

拓展欧拉定理

http://blog.csdn.net/Pedro_Lee/article/details/51458773这篇写的不错

我不会用latex。。。就不写了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000010;
ll p;
int phi[N], pri[N], mark[N];
void Init()
{
    phi[1] = 1;
    for(int i = 2; i <= 10000000; ++i)
    {
        if(!mark[i]) 
        {
            pri[++pri[0]] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= pri[0] && (ll)i * (ll)pri[j] <= 10000000; ++j)
        {
            mark[i * pri[j]] = 1;
            if(i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
        }
    }
}
inline ll power(ll x, ll t, ll p)
{
    ll ret = 1 % p; x %= p;
    for(; t; t >>= 1, x = x * x % p) if(t & 1) ret = ret * x % p;
    return ret;
}
ll f(ll x) // 2^2^2...%p=
{
    if(x == 1) return 0;
    return power(2ll, f(phi[x]) + (ll)phi[x], x);
}
int main()
{
    Init();
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%lld", &p);
        printf("%lld
", f(p));
    }
    return 0;
}