题解 | #好多次方#

题目链接

好多次方 (质数模)

题目描述

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

解题思路

本题要求计算一个嵌套指数对一个固定的质数取模的结果。当模数 $p$ 是质数时，我们可以使用 费马小定理 来简化指数，这比扩展欧拉定理更为直接。

费马小定理

该定理指出，如果 $p$ 是一个质数，而整数 $a$ 不是 $p$ 的倍数（即 $a \not\equiv 0 \pmod p$ ），则有：

$a^{p-1} \equiv 1 \pmod p$

这个性质意味着指数是以 $p-1$ 为周期的。对于任意正整数指数 $E$ ，我们可以将指数对 $p-1$ 取模来降幂。
指数降幂的陷阱与修正

直接使用 $E' = E \pmod{p-1}$ 作为新指数存在一个问题：当 $E$ 恰好是 $p-1$ 的倍数时， $E \pmod{p-1} = 0$ 。这会导致最终计算 $a^0=1$ 。
- 如果 $a \not\equiv 0 \pmod p$ ，这个结果是正确的，因为 $a^{k(p-1)} \equiv (a^{p-1})^k \equiv 1^k \equiv 1 \pmod p$ 。
- 但如果 $a \equiv 0 \pmod p$ ，正确结果应该是 $0$ ，而 $a^0=1$ 则是错误的。
为了解决这个问题，我们需要确保当指数是 $p-1$ 的正倍数时，它被映射到 $p-1$ 而不是 $0$ 。一个严谨的降幂法则是：

$a^E \equiv a^{((E-1) \pmod{p-1}) + 1} \pmod p$

这个公式对所有 $a$ 和 $E \ge 1$ 都成立。
算法流程

令模数 $p = 10^9+7$ 。
- 步骤 1：计算指数 我们需要计算 $a$ 的指数，但只需要它对 $p-1$ 取模的结果。使用快速幂计算 $b^c \pmod{p-1}$ 。但为了应用修正后的公式，我们实际计算的是 $(b^c-1) \pmod{p-1}$ 。这等价于先计算 $b^c$ 的值，再进行模运算。由于 $b^c$ 会非常大，我们不能直接计算。
  
  正确的做法是计算 $exp = \text{power}(b, c, p-1)$ 。
  - 如果 $exp$ 不为 $0$ ，它就是我们想要的指数。
  - 如果 $exp$ 为 $0$ ，说明 $b^c$ 是 $p-1$ 的倍数，此时我们应该使用 $p-1$ 作为指数。
- 步骤 2：计算最终结果 得到简化后的指数 $final\_exp$ 后，再用一次快速幂计算最终结果。 $ans = a^{final\_exp} \pmod p = \text{power}(a, final\_exp, p)$ 。

代码

c++
java
python

#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;

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 = (res * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

void solve() {
    long long a, b, c;
    cin >> a >> b >> c;
    
    long long exp = power(b, c, MOD - 1);
    if (exp == 0) {
        exp = MOD - 1;
    }
    
    cout << power(a, exp, MOD) << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;

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

    private static void solve(Scanner sc) {
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        
        long exp = power(b, c, MOD - 1);
        if (exp == 0) {
            exp = MOD - 1;
        }
        
        System.out.println(power(a, exp, MOD));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc);
        }
    }
}

MOD = 10**9 + 7

def power(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

def solve():
    a, b, c = map(int, input().split())

    exp = power(b, c, MOD - 1)
    if exp == 0:
        exp = MOD - 1

    print(power(a, exp, MOD))

def main():
    try:
        T = int(input())
        for _ in range(T):
            solve()
    except (IOError, ValueError):
        pass

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论、费马小定理、快速幂
时间复杂度：对于每个测试用例，需要进行两次快速幂运算。第一次计算指数，复杂度为 $\mathcal{O}(\log c)$ ；第二次计算最终结果，复杂度为 $\mathcal{O}(\log(\text{MOD}))$ 。因此，每个测试用例的总时间复杂度为 $\mathcal{O}(\log c)$ 。 $T$ 组测试用例的总复杂度为 $\mathcal{O}(T \cdot \log c)$ 。
空间复杂度：算法仅使用有限的几个变量，因此空间复杂度为 $\mathcal{O}(1)$ 。