ex13 倍增求幂

要学习的知识点

倍增求幂
指数的二进制表示
奇偶判断
模运算的乘法性质
时间复杂度约为 O(log n)

题目

练习 13：用倍增法计算 a 的 n 次幂对 m 取模。

输入一行三个整数 a、n、m，其中 n >= 0、m > 0。

参考程序：ex13.py；空白练习：lx13.py。

完整代码

以下内容与 ex13.py 一致，可对照右侧讲解阅读。

"""练习 13：用倍增法计算 a 的 n 次幂对 m 取模。
输入一行三个整数 a、n、m，其中 n >= 0、m > 0。

学习说明：
- 普通逐次乘法需要做约 n 次；倍增法每次把指数除以 2，步骤约为 log2(n)。
- result 累积答案，base 是当前底数的幂，exponent 是还没有处理的指数。
- 指数为奇数时，先把当前 base 乘进 result；随后 base 平方，指数整除 2。
- 每次乘法后都取模，避免计算巨大的完整 a 的 n 次幂。
"""
a, n, m = map(int, input().split())
if n < 0 or m <= 0:
    raise ValueError("要求 n >= 0 且 m > 0")

result = 1 % m
base = a % m
exponent = n
# 指数每轮至少减半，最终会变成 0，循环因而结束。
while exponent > 0:
    if exponent % 2 == 1:
        result = result * base % m
    base = base * base % m
    exponent //= 2

print(result)

进阶写法

这版与初学版解决同一道题，使用更精炼的语法或标准库工具。

进阶源码：ex13_adv.py

"""练习 13 进阶版：使用 pow 的三参数形式计算模幂。"""
a, n, m = map(int, input().split())
if n < 0 or m <= 0:
    raise ValueError("要求 n >= 0 且 m > 0")

print(pow(a, n, m))

pow(a, n, m) 是三参数形式的模幂函数，直接返回 a 的 n 次方对 m 取模；Python 内部使用高效算法，避免生成完整的大整数幂。

运行结果

示例输入：

2 10 1000

程序输出：

逐个认识函数

下表根据程序中实际调用的函数和方法整理；自定义函数的实现与算法细节见后续说明。

函数形式	功能与返回值	注意事项
`ValueError(message)`	内置异常类型，用来表示参数值不符合要求。	raise ValueError(...) 会立即抛错并停止当前程序流程。
`input(prompt='')`	读取一行文本，返回 str；若提供 prompt 会先显示提示。	返回值默认是字符串，计算前通常要做类型转换。
`str.split(sep=None)`	按分隔符拆分字符串，返回字符串列表。	默认按连续空白拆分并忽略首尾空白。
`map(function, iterable)`	逐个应用函数，返回惰性迭代器。	常与 list() 一起使用以立即取得结果。
`print(*objects, sep=' ', end='\n')`	把对象转换为文本显示；返回 None。	默认空格分隔并在末尾换行。

倍增像“分解二进制指数”

普通方法乘 10 次才能得到 2 的 10 次方。倍增法注意到：平方可以一次让指数翻倍；而指数的二进制位决定需要哪些幂。

例如 10 的二进制是 1010，也就是 8+2。因此 2^10 = 2^8 × 2^2。程序维护 result（已选幂的乘积）、base（当前幂）和 exponent（还要处理的指数）：

若指数是奇数，把当前 base 乘进 result。
把 base 平方，相当于把它代表的幂次翻倍。
指数整除 2，扔掉已处理的最低二进制位。
指数变成 0 后，result 就是答案。

每轮指数至少减半，循环次数约为 log₂(n)，比 n 次逐个相乘快很多。

代码中的函数与运算

写法	参数 / 返回 / 含义	注意事项
`input().split()`	读入一行后按空白拆分为字符串列表。	需要恰好输入三个整数。
`map(int, ...)`	把拆出的每项转换为整数；返回 map 迭代器。	左侧三个变量接收三个值。
`a % m`	取余，结果是 a 除以 m 后的余数。	m 必须大于 0；每次乘法后及时取模。
`exponent % 2`	求指数除以 2 的余数。	余数为 1 表示奇数，当前幂需要乘入结果。
`exponent //= 2`	整除赋值，等价于 `exponent = exponent // 2`。	让指数逐轮减半。
`raise ValueError(message)`	主动抛出带说明文字的值错误；不会正常返回。	用于 n<0 或 m<=0 的非法输入。

为什么中途取模不改变最终答案

模运算满足：((x % m) * (y % m)) % m == (x * y) % m。所以我们可以将大乘积缩小到余数范围，最终模值仍正确。特别地，result = 1 % m 也正确处理 m=1 和 n=0。

试算 a=3、n=0、m=7。任何非零数的 0 次方是 1；若 m=1，答案余数是 0。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试指数 n=0、模数 m=1，以及较大的指数；和 pow(a, n, m) 的结果交叉核对。

先在 lx13.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。