快速幂原理以及python内置pow函数

目录

一、前言

二、快速幂

（1）先说说pow函数

（2）快速幂原理

三、题例

（1）上链接

（2）python代码

---

一、前言

对于学计算机的同学来说，学习算法是一件非常重要的事情，废话不多讲，我们来讲讲“快速幂问题”。

二、快速幂

显然Python语言可以不用背快速幂模版，因为自带的pow函数速度已经比快速幂还快了。

但我们仍需要理解原理，因为可能会遇到变种题。

（1）先说说pow函数

描述：

pow() 方法返回 x^y（x的y次方） 的值。

语法：

以下是 math 模块 pow() 方法的语法:

import math

math.pow( x, y )

内置的 pow() 方法：

pow(x, y[, z])
函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z

注意：

pow() 通过内置的方法直接调用，内置方法会把参数作为整型，而 math 模块则会把参数转换为 float。

参数：
x -- 数值表达式。
y -- 数值表达式。
z -- 数值表达式。

返回值：
返回 x^y（x的y次方）的值。

实例：
以下展示了使用 pow() 方法的实例：

import math   # 导入 math 模块
 
print ("math.pow(100, 2) : ", math.pow(100, 2))
# 使用内置，查看输出结果区别
print ("pow(100, 2) : ", pow(100, 2))
print ("math.pow(100, -2) : ", math.pow(100, -2))
print ("math.pow(2, 4) : ", math.pow(2, 4))
print ("math.pow(3, 0) : ", math.pow(3, 0))

以上实例运行后输出结果为：

math.pow(100, 2) :  10000.0
pow(100, 2) :  10000
math.pow(100, -2) :  0.0001
math.pow(2, 4) :  16.0
math.pow(3, 0) :  1.0

（2）快速幂原理

直接看代码就可以明白。

def power(base,exponent): # base : 底数 / exponent : 指数
    res = 1
    while exponent:
        if exponent & 1:  # 判断当前的最后一位是否为1，如果为1的话，就需要把之前的幂乘到结果中。
            res *= base
        base *= base  # 一直累乘，如果最后一位不是1的话，就不用了把这个值乘到结果中，但是还是要乘。
        exponent = exponent >> 1
    return res
 

三、题例

（1）上链接

P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（2）python代码

# 这个方法不能过全部数据，部分会超限
a,b,p=map(int,input().split())
base=a
ex=b
res=1
# print(a," ",b," ",p," ",res)
while b:
    if b&1:
        res=(res*a)%p
    a*=a
    b=b>>1
# print(a," ",b," ",p," ",res)
print("{}^{} mod {}={}".format(base,ex,p,res))
 
# 下面的方法能过
# 用python自带的pow函数速度比上面的快速幂代码快多了
a,b,p=map(int,input().split())
print("{}^{} mod {}={}".format(a,b,p,pow(a,b,p)))

以上，快速幂

祝好