关于对快速幂的一些理解

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 快速幂是什么
• 看看例题
• • 怎么实现快速幂
• 怎么用代码实现
• • 优化
• 结束

  快速幂从名字上来解读就是快速的实现幂运算，但是难道说普通的幂运算不快速吗？
  所以说为什么要用快速幂呢
  这是因为对于普通的幂运算，像直接算或者是c语言中的pow函数都可以用，但是如果幂运算的底数和指数都很大呢，时间上也一定会超时吧。
  这个时候快速幂就发挥了他的作用。

P1226 【模板】快速幂||取余运算
  这是一道题意直接写出来的题目，在刚刚开始我做这道题目的时候，我直接就写了这么一套程序

代码如下（示例）：

int main ()
{
	cin >> a >> b >> p;
	x=1;
	for (int i = 1; i <= b; i++)
		x=x*a%p;
	cout << a << "^" << b << " mod " << p << "=" << x << 'n';
	return 0;
}

  然后也是很简单的过了样例，但是在后面看到数据的范围的时候就发现不是很对了（先读范围很重要！）
他的数据范围很大

  按照平时的算法来算稳稳的超时，所以就卡在那里了
但是这个时候快速幂就派上了用处

  传统的求幂算法时间复杂度非常高（为O(n)），因为当指数n非常大的时候，他的操作数也会变得非常大。而我们快速幂算法通过每一步都把指数分成两半，而相应的底数做平方运算。
这样就可以将原来过于大的指数变小，同时所需要执行的循环次数也变小，而最后表示的结果却一直不会变。让我们先来看一个简单的例子：

2¹⁶=(2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2 × times × 2)
2¹⁶=（2 × times × 2)⁸=4⁸
4⁸=(4 × times × 4)⁴=16⁴
16⁴=(16 × times × 16)²=256²

根据上面那个例子我们很容易就能看出来本来需要算2*2乘16次的通过快速幂就可以轻易的简化到4次，简单来说就是快速幂的时间复杂度为 O(logN)

  看到快速幂的快速了，但是我们怎么用代码来实现这个算法呢
下面是我代码详解

代码如下（示例）：

int pow(int x,int n) //x为底数,n为指数
{
    int sum=1;  //sum为得到的结果
    while (n > 0) {    
        if (n % 2 == 1){
            sum*=x;
        }
        x=x*x;
        n=n/2;
    }
    return sum;
}

在我上面的算法中，每次我都将指数除以2，将底数平方，此时再将结果乘以这个底数，这样最后得到的结果就是像刚才例子所做的步骤相同了

  对于上面的n%2 == 1我们可以通过与运算(&)来实现，这样效率更高
  对于n=n/2，也可以通过将n右移一位来实现
  因此,优化之后的代码实现为:

int pow(int x,int n) //x为底数,n为指数
{
    int sum=1;  //sum为得到的结果
    while (n > 0) {    
        if (n & 1){
            sum*=x;
        }
        x=x*x;
        n=n>>1;
    }
    return sum;
}

  这样我们简单的快速幂就实现了