解题思路

暴力做法:

  • 直接计算 并取模
  • 单次询问时间复杂度：
  • 空间复杂度：
  • 这样会超时，需要使用快速幂算法进行优化。

快速幂原理：

  • 将指数 转换为二进制
  • 根据二进制位计算结果
  • 每次平方并取模

代码

#include <iostream>
using namespace std;

// 快速幂计算 (a^b) % p
long long quickPow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while(b) {
        if(b & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

int main() {
    int q;
    cin >> q;
    
    while(q--) {
        long long a, b, p;
        cin >> a >> b >> p;
        cout << quickPow(a, b, p) << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    static long quickPow(long a, long b, long p) {
        long res = 1;
        a %= p;
        while(b > 0) {
            if((b & 1) == 1) {
                res = (res * a) % p;
            }
            a = (a * a) % p;
            b >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        
        while(q-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long p = sc.nextLong();
            System.out.println(quickPow(a, b, p));
        }
    }
}

def quick_pow(a, b, p):
    res = 1
    a %= p
    while b:
        if b & 1:
            res = (res * a) % p
        a = (a * a) % p
        b >>= 1
    return res

q = int(input())
for _ in range(q):
    a, b, p = map(int, input().split())
    print(quick_pow(a, b, p))

算法及复杂度分析

时间复杂度：

  • 每次快速幂：
  • 次查询： 空间复杂度：

  1. 优化技巧：

    // 初始取模
a %= p;

// 位运算判断奇偶
if(b & 1)

// 右移代替除2
b >>= 1

  2. 注意事项：

    • 数据范围：
    • 中间结果可能溢出
    • 需要使用 long long类型