题解 | 阶幂 # _牛客博客

$[扩展欧拉定理]$

给定 $n$ ，求 $n^{n-1^{n-2^{n-3^{n-4^{n-5^{...}}}}}} \ mod\ (10^{9}+7)$

例如 $n=5$ 时，即求 $5^{4^{3^{2^{1}}}}\ mod\ (10^{9}+7)$

这与上一道题洛谷P4139 上帝与集合的正确用法十分相似，但是仍有区别

推一下这道题目的欧拉公式吧：

定义 $a_{n}=n^{n-1^{n-2^{n-3^{n-4^{...}}}}} \ mod\ m=n^{a_{n-1}}\ mod \ m= n^{a_{n-1}\ mod\ \varphi(m)\ +\ \varphi(m)}\ mod\ m$

所以求 $a_{n-1}\ mod\ \varphi(m)=(n-1)^{a_{n-2}}\ mod\ \varphi(m)=(n-1)^{a_{n-2}\ mod \ \varphi(\varphi(m))\ +\ \varphi(\varphi(m))}\ mod\ \varphi(m)$ .....

可以写出大致的代码：

#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;

int n, m;

int get_oula(int x){
    int sum = x;
    for(int i = 2; i * i <= x; i ++){
        if(x % i == 0){
            sum = sum / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) sum = sum / x * (x - 1);
    return sum;
}

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 n, int m){
    if(m == 1) return 0;
    if(n == 1) return 1;
    else{
        int oula = get_oula(m);
        return ksm(n, dfs(n - 1, oula) + oula, m);
    }
}

signed main(){
    HelloWorld;
    
    cin >> n;
    m = 1000000007;
    cout << dfs(n, m) << endl;
    return 0;
}

洛谷P4139 上帝与集合只有一个参数 $dfs(p)$ ， $p$ 表示的是模数，这是因为洛谷P4139 上帝与集合的底数都是 $2$ 没有变化，而这道题目的底数是 $n$ ，是在变化的

所以 $dfs(n,m)$ ， $n$ 表示当前的底数， $m$ 表示的是当前的模数。

但是错了，原因在于无脑的加上 $oula$

return ksm(n, dfs(n - 1, oula) + oula, m);

扩展欧拉定理是：

$b\leq \varphi(m)$ ， $a^{b}\ mod\ m=a^{m}\ mod \ m$
$b\geq \varphi(m)$ ， $a^{b}\ mod\ m=a^{m\ mod\ \varphi(m)\ +\ \varphi(m)}\ mod \ m$

所以得判断 $b$ 与 $\varphi(m)$ 的关系！！！

为什么洛谷P4139 上帝与集合可以无脑加 $oula$ ，因为洛谷P4139 上帝与集合这道题目的意思就是求解 2 的无限次幂塔模 p，那么2的无限次幂 $2^{ \infty}$ ，指数是 $\infty$ 所以无论什么时候都满足大于 $\varphi(m)$ ，所以无脑加

这里就需要判断大小的关系：

详细解释：

$dfs(n,m)$ 返回的是 $pair<int,bool>$ 类型， $pair.first$ 表示的是 $a_{n}$ 的值， $pair.second$ 表示的是 $a_{n-1}$ 是否大于等于 $\varphi(m)$

当 $m=1$ 时，表示此时需要模上 $1$ ，那么肯定等于 $0$ ；此时 $\varphi(m)=1$ ，所以所有 $a_{n-1}\geq1$ ；返回 $\{ 0,true \}$

当 $n=0$ 时，表示递归到最后一层，那么值就是 $1$ ；此时递归到最后一层，指数没有了，相当于 $a_{n-1}=0$ ，所以 $a_{n-1}<\varphi(m)$ ；返回 $\{ 0,true \}$

$next$ 表示下一层的 $pair<int,bool>$ 类型答案，这样一直递归到最后一层，然后返回时更新答案

$b=next.first$ ，这个 $b$ 就是此时这一层的指数

$next.second$ 就是 $b$ 是否大于 $oula$ ，如果大于那么 $b= b+oula$

$now\_ans$ 计算当前这一层的 $a_{n}$ 值

$ans\_ans\_bool$ 表示当前这一层的指数 $b$ 是否大于 $oula$

pair<int, bool> dfs(int n, int m){
    if(m == 1) return {0, true};
    if(n == 1) return {1, false};
    else{
        int oula = get_oula(m);
        pair<int, bool> next = dfs(n - 1, oula);
        int b = next.first;
        if(next.second) b += oula;
        int now_ans = ksm(n, b, m);
        bool now_ans_bool = b >= oula;
        return {now_ans, now_ans_bool};
    }
}

总代码：

#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;

int n, m;

int get_oula(int x){
    int sum = x;
    for(int i = 2; i * i <= x; i ++){
        if(x % i == 0){
            sum = sum / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) sum = sum / x * (x - 1);
    return sum;
}

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;
}

pair<int, bool> dfs(int n, int m){
    if(m == 1) return {0, true};
    if(n == 1) return {1, false};
    else{
        int oula = get_oula(m);
        pair<int, bool> next = dfs(n - 1, oula);
        int b = next.first;
        if(next.second) b += oula;
        int now_ans = ksm(n, b, m);
        bool now_ans_bool = b >= oula;
        return {now_ans, now_ans_bool};
    }
}

signed main(){
    HelloWorld;
    
    cin >> n;
    m = 1000000007;
    cout << dfs(n, m).first << endl;
    return 0;
}