1、入门小谈

假如让你求3的6次方后三位，这个程序毫无疑问是非常简单的：

//求幂运算
long long test(int base,long long po)
{
	int result = 1;
	for(int i=0;i<po;++i) result*=base;
	return result%1000;
}
int main()
{	
	int r = test(3,6);
	cout<<r<<endl;
	return 0;
}

但是假如让你求3的100次方的后三位呢？
如果我们还使用上面的程序的话，结果会是0。原因就在于3的100次方是个很大的数，大到long long类型都无法表示。

1.1 取模运算

针对上述情况，其实我们只要在每一次的运算结果后面取模就可以了。原因就在于取模的计算方式： (a * b) % p = (a % p * b % p) % p 。所以我们可以对上述程序进行改动：

long long test(int base,long long po)
{
	int result = 1;
	for(int i=0;i<po;++i) 
	{
		result*=base;
		result = result%1000;
	}
	return result%1000;
}
int main()
{	
	int r = test(3,100);
	cout<<r<<endl;
	return 0;
}

好的，我们现在解决了上述的问题，但是上述代码的时间复杂度却令我们不太满意，假如求base的n次方，这个复杂度就是O（n）。如果让你求3的100000000000次方，那么程序运行时间会很长。这个做法在很多题中都会超时的。那么有没有一种做法可以优化我们的时间复杂度呢？快速幂算法登场了！

2、快速幂简介

快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高，就是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
举个例子：

求3^20。如果使用传统的算法：我们需要循环20次。但是利用快速幂，我们可以把3^20分解为（3^2）^10=9^10。我们下一次求9^10放可以分解为（9^2）^5=81^5。每次运算都把底数变为平方，指数变为一半。每一次的快速幂操作都减少了一半的循环量！

如果幂次为奇数该怎么做呢？

比如求3^19次方，我们可以把3^19变为3*3^18,然后对3^18运用快速幂即可。

3、快速幂代码实现

    long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
          	//幂次是奇数的话每次分离出一个base，然后对剩下的进行快速幂运算
            result = result * base % 1000; 
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
    }
    return result;
}

快速幂核心：
（1）幂次若是偶数：每次运算，底数变平方、幂次变一半；
（2）幂次若是奇数：每次运算，先分离出一个base（底数），然后底数变平方、幂次变一半；