BZOJ3884上帝与集合的正确用法

题目链接

BZOJ

洛谷

解析

欧拉定理及扩展欧拉定理：
\[ a^b \equiv \begin{cases} a^{b \ mod \ \phi(p)}, & \gcd (a, p) = 1 \\ a^b, & \gcd(a, p) \ne 1, &b < \phi(p) \\ a^{b \ mod \ \phi(p) + \phi(p)}, & \gcd(a, p) \ne 1, & b \ge \phi(p) \end{cases} \ (mod \ p) \]
然后其实可以把第一个和第三个合起来得到\(a^b \equiv a^{b \ mod \ \phi(p) + \phi(p)} (mod \ p),b \ge \phi(p)\)

令题目要求的\(2^{2^{2^{2^{..}}}}mod \ p\)为\(f(p)\)，那么\(f(p) = 2^{f(\phi(p)) + \phi(p)} (mod \ p)\)

于是线性筛出\(\phi\)，递归地求\(f\)即可，边界条件是\(f(1) = 0\)

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MAXP 10000005

typedef long long LL;
int phi[MAXP], T, P;

void make_phi();
int calc(int);
int main() {
    make_phi();
    std::ios::sync_with_stdio(false);
    std::cin >> T;
    while (T--) {
        std::cin >> P;
        std::cout << calc(P) << std::endl;
    }
    return 0;
}
void make_phi() {
    static char isn_prime[MAXP];
    static std::vector<int> prime;
    phi[1] = 1;
    for (int i = 2; i <= MAXP; ++i) {
        if (!isn_prime[i]) {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; j < prime.size() && (LL)i * prime[j] <= MAXP; ++j) {
            isn_prime[i * prime[j]] = 1;
            if (i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            else { phi[i * prime[j]] = phi[i] * prime[j]; break; }
        }
    }
}
int qpower(int x, int y, int p) {
    int res = 1;
    while (y) {
        if (y & 1) res = (LL)res * x % p;
        x = (LL)x * x % p;
        y >>= 1;
    }
    return res;
}
int calc(int p) {
    if (p == 1) return 0;
    return qpower(2, calc(phi[p]) + phi[p], p);
}
//Rhein_E