题解 | 洛谷P4139 上帝与集合的正确用法 #

$[扩展欧拉定理]$

定义 $a_{0} = 1,a_{n} =2^{a_{n}-1}$ ，可以证明 $b_{n}=a_{n}\ mod\ p$ ，在某一项后都是同一个值，求这个值

$a_{0}=1$

$a_{1}=2^{a_{0}}=2^{1}$

$a_{2}=2^{a_{1}}=2^{2^{1}}$

$a_{3}=2^{a_{2}}=2^{2^{2^{1}}}$

$a_{4}=2^{a_{3}}=2^{2^{2^{2^{1}}}}$

....

$a^{n}=2^{a_{n-1}}=2^{2^{2^{2^{2^{...}}}}} \ mod\ p$

即求解 2 的无限次幂塔模 p，利用扩展欧拉定理递归简化幂运算，同时通过线性筛（欧拉筛） 预处理欧拉函数值，保证计算效率

$a_{n}\ mod\ p=2^{a_{n-1}}\ mod\ p=2^{(a_{n-1}\ mod\ \varphi(p))\ +\ \varphi(p)}\ mod \ p$ ，所以转化为求 $a_{n-1}\ mod\ \varphi(p)$

同样的： $a_{n-1}\ mod\ \varphi(p)=2^{a_{n-2}}\ mod\ \varphi(p) = 2^{(a_{n-2}\ mod\ \varphi(\varphi(p))) \ +\ \varphi(\varphi(p))}\ mod\ \varphi(p)$ ，.....

所以容易看出是个递归问题，可用 $DFS$ 搜索解决，递归到最后情况是 $\varphi(p)=1$ ，即 $mod\ 1$ ，所以返回结果 $0$ ，这也是为什么题目说可以证明在某一项后都是同一个值

因为 $DFS$ 频繁用到 $\varphi(p)$ ，又是多组测试数据，所以同时通过线性筛（欧拉筛）预处理欧拉函数值：

const int N = 1e7 + 10;

int prime[N], idx;
bool st[N];
int oula[N];

void get_prime_oula(){
    memset(st, false, sizeof(st));
    memset(oula, 0, sizeof(oula));
    idx = 0;
    oula[1] = 1;
    for(int i = 2; i <= N; i ++){
        if(!st[i]){
            prime[++ idx] = i;
            oula[i] = i - 1;
        }
        for(int j = 1; prime[j] <= N / i; j ++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0){
                oula[i * prime[j]] = oula[i] * prime[j];
                break;
            }
            else oula[i * prime[j]] = oula[i] * oula[prime[j]];
        }
    }
}

解释这段代码：

if(i % prime[j] == 0){
    oula[i * prime[j]] = oula[i] * prime[j];
    break;
}
else oula[i * prime[j]] = oula[i] * oula[prime[j]];

如果找到质数 $prime[j]$ 是 $i$ 的最小质因子，那么就 $break$ ，这就是为什么线性筛时间复杂度为 $O(n)$ 的原因

不过这次是与求所有数的欧拉函数一起的：

欧拉定理的两个公式：

如果 $a$ 是 $b$ 的一个质因子，那么 $\varphi(a\times b) = \varphi(b) \times a$
如果 $a$ 与 $b$ 互质，那么 $\varphi(a\times b) = \varphi(a) \times \varphi(b)$

分别对应里面的两行代码

$DFS$ 求解过程：没有什么好说的

int dfs(int p){
    if(p == 1) return 0;
    else return ksm(2, dfs(oula[p]) + oula[p], p);
}

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e7 + 10;

int prime[N], idx;
bool st[N];
int oula[N];

void get_prime_oula(){
    memset(st, false, sizeof(st));
    memset(oula, 0, sizeof(oula));
    idx = 0;
    oula[1] = 1;
    for(int i = 2; i <= N; i ++){
        if(!st[i]){
            prime[++ idx] = i;
            oula[i] = i - 1;
        }
        for(int j = 1; prime[j] <= N / i; j ++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0){
                oula[prime[j] * i] = oula[i] * prime[j];
                break;
            }
            else oula[prime[j] * i] = oula[i] * oula[prime[j]];
        }
    }    
}

int ksm(int a, int b, int mod){
    a %= mod;
    int sum = 1;
    while(b){
        if(b & 1) sum = (sum * a) % mod;
        b >>= 1;
        a = (a * a) % mod;  
    }
    return sum;
}

int dfs(int p){
    if(p == 1) return 0;
    else return ksm(2, dfs(oula[p]) + oula[p], p);
}
signed main(){
    HelloWorld;
    
    get_prime_oula();   
    int tt; cin >> tt;
    while(tt --){
        int p; cin >> p;
        cout << dfs(p) << endl;
    } 
    return 0;
}