快速幂运算

快速幂运算
最近看到的一些题里有利用快速矩阵幂来求快速解递归函数(比如Fibonacci数列),在很久之前看和RSA算法里也涉及到了快速求幂的算法,所以今天就想一块来介绍一下。 在介绍开始之前,先对本文的算法做一个声明,下文所提到的幂运算的指数n,满足条件n >= 0,这一点非常重要。 首先幂运算,大家其实都很好理解,其实就是: 无非就是把一个数自乘n次,所以我们通常计算数字的幂的算法就是: (代码1) [crayon-5a5eb80bef431653468038/] 这个算法很简单,其复杂度是O(n)的,一般来说,这样的复杂度并不会使我们困惑,但是一般应用幂运算的地方,指数都会非常非常的大,比如1 000 000 000这个级别的,这时候我们会遇到两个问题,第一个就是我们不能再用int来存储整数,必须用高精度整数类型来进行存储,另一个就是在指数是如此变态的数量级之下,我们的计算量会骤然上升,结果也会异常惊人的大。 快速幂算法就是为了解决这个问题而发明的,其实它本身很简单,就是利用二分法,在具体介绍...