二分法的常见应用

1. 计算 an （数的幂）

2. 计算 An （矩阵的幂）

由于矩阵乘法具有结合律，因此
A4=A∗A∗A∗A=(A∗A)∗(A∗A)=A2∗A2
我们可以得到这样的结论：

• 当n为偶数时， An=An/2∗An/2
• 当n为奇数时， An=An/2∗An/2∗A （其中n/2取整）。

这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即可。

根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。