1.普通的求幂方法：

时间复杂度为O(n),对于比较大的数在1s限时内可能会TLE

int pow(int base,int p）{

       int ans=1;

       for(int i=1;i<=p;i++)

          ans*=base;

       return ans;

}

2.快速幂：

时间复杂度为logn

（1）结合位运算

原理：指数p可转化为2进制形式

　　则base^p=baseⁱ^(1)*^{2^0+i(2)*2^1+i(3)*2^2+……}

=base^{ⁱ^(1)*^{2^0}}*base^{i(2)*2^1}*base^{i(3)*2^2}*……

当i(n)=0时相当于乘了1，也就相当于什么也没乘，而每次待乘的数都是base^{2^k},乘不乘由系数i(k+1)决定，但不管乘不乘，下一次待乘的数都是base^{2^(k+1)}即base^{2*2^k}也就是(base^{2^k})²。

代码实现：

long long fastpow(long long base,long long p){

        long long ans=1;

        while(p!=0){

               if(p&1!=0)//如果这一位(二进制最后一位)为1，则乘上待乘的数(或P%2==1)

                      ans*=base;

               base*=base;

               p>>=1;(或者p/=2)

         }

         return ans;

}

(2)结合模运算

我们知道base^p%d=(base%d)*(base%d)*(base%d)*……%d

　　　　　　　　=(base%d)^p%d

上代码：

 long long fastpowmod(long long base,long long p,long long d){

                long long ans=1;

                base%=d;

                while(p!=0){

                        if(p&1!=0)

                                ans=ans*base%d;

                        base=base*base%d;

                        p>>=1;

                }
　　　　　　　　　　ans%=d;//0次方特判

                return ans;

}

巴特西

求幂&&快速幂&&位运算

1.普通的求幂方法：

2.快速幂：

（1）结合位运算

(2)结合模运算

最新文章

热门文章