Luogu 4139 上帝与集合的正确用法

扩展欧拉定理：$a^{b} \equiv a^{b Mod \varphi  (p) + \varphi  (p)}  (Mod  p)  $ $(b \geq \varphi (p))$ 。

这道题中$\varphi (p)$一定是一个偶数，所以余数为$0$。

这样子的话只需要递归求解就可以了，可以知道一定不会超过$log$层。

时间复杂度$O(maxN + Tlognlogn)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e7 + ;

int testCase, pCnt, pri[N];

ll n, phi[N];

bool np[N];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

void sieve() {

    phi[] = 1LL;

    for(int i = ; i < N; i++) {

        if(!np[i]) pri[++pCnt] = i, phi[i] = i - ;

        for(int j = ; j <= pCnt && i * pri[j] < N; j++) {

            np[i * pri[j]] = ;

            if(i % pri[j] == ) {

                phi[i * pri[j]] = phi[i] * pri[j];

                break;

            }

            phi[i * pri[j]] = phi[i] * (pri[j] - );

        }

    }

}

inline ll pow(ll a, ll b, ll P) {

    ll res = 1LL;

    for(; b > ; b >>= ) {

        if(b & ) res = res * a % P;

        a = a * a % P;

    }

    return res;

}

ll solve(ll now) {

    if(now == ) return ;

    return pow(2LL, phi[now] + solve(phi[now]), now);

}

int main() {

    sieve();

    for(read(testCase); testCase--; ) {

        read(n);

        printf("%lld\n", solve(n));

    }

    return ;

}