快速幂(C语言)

2023-12-13 23:32:23

前言
快速幂算法一般用于高次幂取模的题目中,比如求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;
}

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

文章来源:https://blog.csdn.net/Tokai___Teio/article/details/134891564
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。