快速幂算法

快速幂算法

【二进制快速幂】

比如我们计算pow(3,5)，将5改写成二进制101，我们可以将算法过程写成以下形式：

这就将原本的4次乘法改成了2次乘法，其次我们将每个乘积项设成x，每次对x进行平方，从而构造下一个乘积项。当二进制的当前位为1时，将当前乘积项x乘入最终结果，否则不乘入最终结果（即当前乘积项为1）。

可借助位运算来实现：

n表示当前指数n & 1//判断n最后一位的奇偶，奇数则说明需要把当前乘积项x乘入最终结果n>>=1//把 n 的二进制右移一位，并赋给当前的n，最后一位为1，则需要将当前乘积项乘入最终结果

还需要注意的是，当指数n为负数时，我们将底数改造成倒数，在把指数改造成正数。 如果直接对负数进行移位操作，会有很多不符合预期的地方 比如当前指数是-1，-1的反码为全1，右移后高位补符号位，仍是全1，当前指数不变，不会变成0，循环不会退出

double myPow(double x, int n) { double res = 1; long long b = n; if( b < 0 ){ x = 1 / x; b = -b; //直接把int的负数取反会溢出，由于b的值只有int范围，所以不会溢出 } while(b){ //当前位为1时，需要把这时的X计入结果 if( b & 1 ){ res *= x; } x *= x;//构造下一个乘积项 b >>= 1; } return res;}

快速幂递归写法

和上述的迭代写法效率一样

double getPow(double x, int b){ if( b == 0 ) return 1; //设置出口 double temp = getPow(x,b>>1); return b & 1 ? temp * temp * x : temp * temp; } double myPow(double x, int n) { long long b = n; if(b < 0){ b = -b; x = 1 / x; } double temp = getPow(x,b>>1); return b & 1 ? temp * temp * x : temp * temp; //判断n的奇偶 }

关于快速幂的取模公式

公式1：

公式2：

这题主要用到公式2和快速幂

#includeusing namespace std;const long long mod = 1e9+7;int main(){ int n; long long x = 3; long long res = 1; while(cin >> n){ while(n){ if(n & 1){ res = ((res % mod) * (x % mod)) % mod;//最终结果每次也取模 } //将每次的乘积项取模 x = ((x % mod) * (x % mod)) % mod;//之前x定义为int，这里会溢出 n >>= 1; } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。