快速幂（C语言）

前言
快速幂算法一般用于高次幂取模的题目中，比如求3的10000次方对7取模。这时候有些同学会说：这还不简单？我直接调用pow函数然后对结果%7不得了么？可是3的10000次方这么庞大的数字，真的能储存在计算机里么？显然是不行的，只会得到一个错误的数字，那么我们怎样才能得到答案呢？首先我们要知道取模的运算法则。
( a * b ) % c = ( ( a % c ) * ( b % c ) ) % c (要是不知道为什么请自行百度）
在了解了取模的运算法则后就让我们进入今天的正题吧！

快速幂
既然我们知道了取模的运算法则，那么3的一万次方%7转化成（（（3%7）*3）%7）*3）%7…
这样便不会出现数字太大超出范围的情况。这一种我们可以采用循环的方法实现。

#include<stdio.h>
int main()
{
	int a = 3, b = 10000;
	int ans = 1;
	while (b--)
	{
		ans = ans * a % 7;
	}
	printf("%d\n", ans);
	return 0;
}

可是这样要进行一万次的循环，效率非常之低，这时就需要用到我们的快速幂算法。
首先3的一万次方=9的5千次方=81的2500次方…以此类推。如果我们对底数平方处理，那么我们只需要将幂除以2即可。这样能极大地提高效率，但是要注意特殊情况，比如3的10001次方此时10001并不是一个偶数，但是我们可以把它变成偶数，可以变为3*3的一万次方，也就是说我们在进行快速幂算法时要考虑幂的奇偶情况。
下面我用代码来为大家展示。

#include<stdio.h>
int main()
{
	int a = 3, b = 10000;
	int ans = 1;
	while (b)//当b大于0时进行循环
	{
		if (b%2==1)
			ans = ans*a%7;
		b /= 2;
		a = a*a%7;
	}
	printf("%d", ans);
	return 0;
}

那么有没有更快的方式呢？当然有，我们知道使用位操作符和移位操作符的运算速度比使用/和%要快上好多。那么我们就可以对代码进行这样的修改。

#include<stdio.h>
int main()
{
	int a = 3, b = 10000;
	int ans = 1;
	while (b)
	{
		if (1 & b)//若果1&b=1说明b是奇数，如果1&b=0说明b是偶数
			ans = ans*a%7;
		b >>= 1;//相当于b=b/2
		a = a*a%7;
	}
	printf("%d", ans);
	return 0;
}

这就是快速幂算法，如果觉得博主讲得不错请给博主一个赞支持一下吧~（如果能再收藏一下就更好了），那么今天的分享就到这里，我们下期再见！