题解 | 乘方取模

解题思路

基本思路：
- 使用快速幂算法计算 $a^b \mod m$ 。
- 通过二进制拆分指数 $b$ 来减少计算次数。
- 在计算过程中同时进行取模运算，避免溢出。
实现方法：
- 将指数 $b$ 转换为二进制形式。
- 根据二进制位为1的位置进行累乘。
- 每次乘法后立即取模，保证中间结果不会溢出。

代码

cpp
java
python

#include <iostream>
using namespace std;

long long quick_pow_mod(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;  // 先对a取模
    
    while (b > 0) {
        if (b & 1) {  // 如果b的当前位为1
            result = (result * a) % m;
        }
        a = (a * a) % m;  // 更新a为a^2
        b >>= 1;  // b右移一位
    }
    
    return result;
}

int main() {
    long long a, b, m;
    cin >> a >> b >> m;
    cout << quick_pow_mod(a, b, m) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static long quickPowMod(long a, long b, long m) {
        long result = 1;
        a %= m;  // 先对a取模
        
        while (b > 0) {
            if ((b & 1) == 1) {  // 如果b的当前位为1
                result = (result * a) % m;
            }
            a = (a * a) % m;  // 更新a为a^2
            b >>= 1;  // b右移一位
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long m = sc.nextLong();
        
        System.out.println(quickPowMod(a, b, m));
    }
}

def quick_pow_mod(a, b, m):
    result = 1
    a = a % m  # 先对a取模
    
    while b > 0:
        if b & 1:  # 如果b的当前位为1
            result = (result * a) % m
        a = (a * a) % m  # 更新a为a^2
        b >>= 1  # b右移一位
    
    return result

if __name__ == "__main__":
    a, b, m = map(int, input().split())
    print(quick_pow_mod(a, b, m))

算法及复杂度

算法：快速幂取模
时间复杂度： $\mathcal{O}(\log b)$ ，其中 $b$ 为指数
空间复杂度： $\mathcal{O}(1)$