「Luogu P4139」上帝与集合的正确用法

Description

给定 $T\ (T\leq 10^3)$ 组数据，每组数据包含一个正整数 $p\ (1 \leq p \leq 10^7)$，求 $2^{2^{2 \cdots}}(无限个 2) \bmod p$ 的值。

Source

[Luogu]P4139

Solution

前置知识：

常见积性函数 - 欧拉函数 - 线性筛求欧拉函数

常用的质数相关定理 - 扩展欧拉定理

在此题中，指数 $b = 2^{2^{2\cdots}}$ 一定满足 $b \geq \varphi(p)$，所以我们通过 扩展欧拉定理：

$$\begin{aligned} a^b &\equiv a^{b \bmod \varphi(p) + \varphi(p)} \pmod p & b \geq \varphi(p)\\ \end{aligned}$$

得到

$$2^{2^{2\cdots} } \bmod p=2^{\left(2^{2 \cdots} \bmod \varphi(p)+\varphi(p)\right)} \bmod p$$

设 $f(p) = 2^{2^{2\cdots}} \bmod p$，则有

$$f(p)=2^{f(\varphi(p)) + \varphi(p)}\bmod p$$

我们就成功地化简了问题——把求 $f(p)$ 转化为求 $f(\varphi(p))$ 。

这个式子可以一直递归下去，直到 $p = 1$ 时返回 $f(1)=2^{2^{2 \cdots}} \bmod \varphi(1) = 0$ 。总时间复杂度为 $O(p + T\log^2 p)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e6, MAXP = 1e7;
int t, p, cnt, prime[MAXN + 5], phi[MAXP + 5];
bool isNotPrime[MAXP + 5];

inline void getPhi(int n) {
    phi[1] = 1;
    isNotPrime[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isNotPrime[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            isNotPrime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}//线性筛求 φ(1) ~ φ(n) 

inline int quickPow(int x, int p, int mod) {
    int res = 1;
    for (; p; p >>= 1, x = (LL) x * x % mod)
        if (p & 1)
            res = (LL) res * x % mod;
    return res;
}//快速幂 

int f(int p) {
    if (p == 1) return 0;//f(1) = 0
    return quickPow(2, f(phi[p]) + phi[p], p);
}//递归求解 

int main() {
    getPhi(MAXP);
    for (read(t); t; --t) {
        read(p);
        write(f(p));//答案为 f(p) 
        putchar('\n');
    }
    return 0;
}