首页 > 代码库 > 快速幂[分治]

快速幂[分治]

快速幂

——!x^n+y^n=z^n

  我们在编写程序中常常会碰到求解a^p 的情况,这时候如果只是简单的遍历一遍会浪费很多时间,这时候我们就需要快速幂了。

  其实快速幂的操作非常简单,比如我们要求a^p,我们只需求 a^(p/2),再平方就行了,如果p为奇数,那我们只需在乘一个p即可。

  在此主要介绍一种用位运算处理的快速幂:

我们考虑 a^p ,如果我们用二进制来看待p 假设为(10101)2,即为1+0*2^1+1*2^2...。意思就是说我可以这样来表示:

      a^(10000)2*a^(100)2*...

我们注意到只需把这个二进制位有1的部分乘入答案即可,并且a^(1<<i)=(a^(1<<(i-1)))^2,那么利用这一特性我们就能简洁漂亮地得到一种快速幂的写法。

  附上Lowbee的代码

 

int fpow(int a,int p){    int res=1,base=a;    while(p>0){        if(p&1)            res*=base;        base*=base;        p>>=1;    }    return res;}

 

 

 

 

快速幂[分治]