蒟蒻学习快速幂笔记

我基本是在刷题中学习的算法，所以基本学的算不上系统，也可能说不上全面

为了防止遗忘，学习了的东西就通过博客记录下来吧。

快速幂

旨在减少计算次数，可以将O(n)--->O(logn);

减少时间复杂度

a^b

例如：2^13:一般方法是循环相乘13次，但是利用二进制，可以将幂次13改写为二进制1101；于是2^13--->2^(1*2^0+0*2^1+1*2^2+1*2^3);只需要计算4次！！！

代码：

int fast_pow(int a,int b)
{
    int ans=1;int base=a;
    while(b!=0)
    {
        if(b&1!=0)//b二进制上最后一位为1，不为0
            ans*=base;
        base*=base;
        b>>=1;//b的二进制数向右移一位
        return ans;          
    }

由于指数函数是爆炸增长的函数，所以很有可能会爆掉int的范围，根据题意选择 long long还是mod某个数。

或者在快速幂的原理下，采用高精度乘法！

如果题目中有要求取模就取模 乘法的取模：( a * b ) mod c==( ( a mod c ) * ( b mod c) ) mod c;

蒟蒻学习快速幂笔记

原文：https://www.cnblogs.com/PoRain/p/10705359.html