快速幂算法 (Python 和 C++ 实现)

快速幂算法是一种高效计算 a^b mod m 的算法，其中 a, b, m 为整数。该算法利用二进制分解的思想，将 b 分解成二进制表示，然后利用递归或循环进行计算。

Python 实现

def ksm(n_,p_,m_):
    res = 1
    n,p,m = n_,p_,m_
    while p:
        if p % 2 == 1:
            res = res * n % m
        n = n * n
        m = m / 2
    return res

a,b,c = int(input()),int(input()),int(input())
print(ksm(a,b,c))

C++ 实现

#include<iostream>
using namespace std;

int ksm(int n, int p, int m){
    long long res = 1;
    long long nn = n, mm = m;
    while(p){
        if(p % 2 == 1){
            res = (res * nn) % mm;
        }
        nn = (nn * nn) % mm;
        p = p / 2;
    }
    return res;
}

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << ksm(a, b, c) << endl;
    return 0;
}

代码解析

1. Python 代码解析

   • 函数 ksm(n_,p_,m_) 用于计算 n^p mod m。
   • 变量 res 初始化为 1，用于存储计算结果。
   • 使用 while 循环，遍历 b 的二进制表示，若当前位为 1，则将 res 乘以 n 并取模 m；否则，将 n 平方并取模 m。
   • 返回最终结果 res。

2. C++ 代码解析

   • 函数 ksm(n, p, m) 用于计算 n^p mod m。
   • 变量 res 初始化为 1，用于存储计算结果。
   • 使用 while 循环，遍历 b 的二进制表示，若当前位为 1，则将 res 乘以 n 并取模 m；否则，将 n 平方并取模 m。
   • 返回最终结果 res。

应用场景

快速幂算法可以应用于多种场景，例如：

• 计算大数的余数
• 密码学中的加密和解密
• 矩阵快速幂等

总结

本文介绍了快速幂算法的原理和实现，并提供了 Python 和 C++ 代码示例。通过本文，读者可以理解快速幂算法的工作原理，并将其应用于实际的编程问题中。