题解 | #好多次方#

题目链接

HIGH19 好多次方

题目描述

给定 $T$ 组数据，每组数据给出三个正整数 $a, b, c$ ，请你计算以下表达式的值： $a^{b^c} \pmod{10^9 + 7}$

输入描述: 第一行输入一个整数 $T$ ，表示测试组数。接下来 $T$ 行，每行输入三个整数 $a, b, c$ 。

输出描述: 对于每组数据，在一行上输出一个整数，代表式子的答案。

解题思路

本题要求计算一个“幂塔”或“超级幂”： $a^{b^c} \pmod p$ ，其中 $p=10^9+7$ 是一个固定的质数。核心的挑战在于指数 $b^c$ 会变得非常大，无法直接计算。解决这个问题的关键是 欧拉降幂定理。

欧拉降幂定理

该定理是欧拉定理的推广，它不要求底数和模数互质，因此是解决此类问题的通用工具。其内容如下： $a^k \pmod m = \begin{cases} a^k \pmod m & \text{if } k < \phi(m) \\ a^{k \pmod{\phi(m)} + \phi(m)} \pmod m & \text{if } k \ge \phi(m) \end{cases}$

其中 $\phi(m)$ 是 欧拉函数。因为本题的模数 $p=10^9+7$ 是一个质数，所以 $\phi(p) = p - 1 = 10^9+6$ 。

算法步骤

定义常量： $p = 10^9 + 7$ $\phi(p) = p - 1 = 10^9 + 6$
实现带比较的快速幂 power_capped(base, exp, cap)：这个函数的目的是判断 $b^c$ 是否小于 $\phi(p)$ 。它在计算 $base^{exp}$ 的过程中，如果中间结果已经大于或等于 cap，就立刻返回 cap，表示 $b^c \ge \phi(p)$ 。否则返回真实的计算结果。
主逻辑：对于每组查询 $a, b, c$ : a. 使用 power_capped(b, c, phi(p)) 判断 $b^c$ 与 $\phi(p)$ 的大小关系。 b. 计算指数：
- 如果 power_capped 的返回值小于 $\phi(p)$ ，说明 $b^c < \phi(p)$ 。最终的指数 final_exp 就是 $b^c$ 本身。
- 否则，说明 $b^c \ge \phi(p)$ 。最终的指数 final_exp 应该是 pow(b, c, phi(p)) + phi(p)。 c. 计算结果：使用标准快速幂计算 pow(a, final_exp, p)。

关于代码的说明: 您可能注意到下面的 C++/Java/Python 代码中都包含了一个 phi 函数的实现，尽管在本题中我们直接使用了 p-1 这个常量。这是为了让这份代码成为一个更通用的 欧拉降幂模板。在更一般的问题中，模数 $m$ 可能不是质数，此时就需要动态计算 $\phi(m)$ ，这个 phi 函数就可以直接派上用场。

代码

cpp
java
python

#include <iostream>

using namespace std;

const int P = 1e9 + 7;
const int PHI_P = 1e9 + 6;

// 欧拉函数 (模板)
long long phi(long long n) {
    long long result = n;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

// 计算 min(base^exp, cap)，用于比较 b^c 和 phi(P) 的大小
long long power_capped(long long base, long long exp, long long cap) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            if ((__int128)res * base >= cap) return cap;
            res = res * base;
        }
        if (exp > 1) {
            if (base > 0 && (__int128)base * base >= cap) return cap;
            base = base * base;
        }
        exp /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        long long a, b, c;
        cin >> a >> b >> c;
        
        long long exp;
        long long bc_capped = power_capped(b, c, PHI_P);

        if (bc_capped < PHI_P) {
            exp = bc_capped;
        } else {
            exp = power(b, c, PHI_P) + PHI_P;
        }
        
        cout << power(a, exp, P) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int P = 1_000_000_007;
    static final int PHI_P = 1_000_000_006;

    // 欧拉函数 (模板)
    public static long phi(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }

    public static long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    public static long powerCapped(long base, long exp, long cap) {
        long res = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                if (base != 0 && res > cap / base) return cap;
                res *= base;
                if (res >= cap) return cap;
            }
            if (exp > 1) {
                if (base != 0 && base > cap / base) return cap;
                base *= base;
                if (base >= cap) return cap;
            }
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();

            long exp;
            long bcCapped = powerCapped(b, c, PHI_P);
            
            if (bcCapped < PHI_P) {
                exp = bcCapped;
            } else {
                exp = power(b, c, PHI_P) + PHI_P;
            }
            
            System.out.println(power(a, exp, P));
        }
    }
}

import sys

P = 10**9 + 7
PHI_P = 10**9 + 6

# 欧拉函数 (模板)
def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

def power_capped(base, exp, cap):
    res = 1
    # base 不需要对 cap 取模，因为我们关心的是真实值与 cap 的比较
    while exp > 0:
        if exp % 2 == 1:
            if base == 0: # 特殊情况
                return 0
            # 乘法前检查是否溢出
            if res > cap / base:
                return cap
            res *= base
            if res >= cap:
                return cap
        if exp > 1:
            if base == 0: # 特殊情况
                pass
            # 乘法前检查是否溢出
            elif base > cap / base:
                return cap
            base *= base
            if base >= cap:
                 return cap
        exp //= 2
    return res

def solve():
    T = int(input())
    for _ in range(T):
        a, b, c = map(int, input().split())
        
        bc_capped = power_capped(b, c, PHI_P)
        
        if bc_capped < PHI_P:
            exp = bc_capped
        else:
            exp = pow(b, c, PHI_P) + PHI_P
            
        print(pow(a, exp, P))

solve()

算法及复杂度

算法：欧拉降幂定理 + 快速幂
时间复杂度： $\mathcal{O}(T \cdot \log c)$ ，对于每个测试用例，主要开销来自于计算指数的几次快速幂。
空间复杂度： $\mathcal{O}(1)$ 。