快速乘法/幂算法详解_(a * b) % mod-程序员宅基地

快速乘法/幂算法详解

适用范围：快速计算a*b % mod的结果（主要目的是换乘法为加法，防止爆数据），或者快速计算a^b % mod 的结果，时间复杂度大大降低。

算法描述：首先你可能会问a*b不是直接乘就出来了么，为什么需要快速算法？但是乘法在计算机中处理的时间并不是这么快的，也要拆分为加法来做的。所以快速乘法会更快的计算a*b的结果，而且a*b%mod可能还没取模就已经爆long long，但快速乘法却不会。快速幂也是同样的道理。

实现的原理都是基于按照二进制位一步一步乘来避免重复的操作，利用前面的中间结果，从而实现快速的目的。

对于乘数b来说，势必可以拆成2进制，比如110101。有一些位为0，有一些位为1。根据乘法分配律：a*b=a*（b1+b2+b3+…… ）

那么对于a*53 = a*110101（二进制）= a*（100000+10000+100+1）=a*（100000*1+10000*1+1000*0+100*1+10*0+1*1）。

那么设立一个ans=0用于保存答案，每一位让a*=2，在根据b的对应为1看是不是加上此时的a，即可完成快速运算。比如刚才的例子让a=5，运转流程如下。

即可计算出5*53=265。

不知道看到这里你发现了没有，其实对于快速幂其实是一样的道理，只不过每一位a更新的时候不是*2，而是a=a*a，ans+变成ans*。

例如3^9的流程如下：3^5=3^(1001) （二进制）= 3^(1000*1+100*0+10*0+1*1)

最后说一些细节吧，如果要取模在ans+、ans*、和a更新的时候都%mod即可。然后b一位一位的读取每次b/=2或者b>>=1，表示b向右移动一位，再与1做&操作即可。（见代码）

上代码：

#include <iostream> 
#include <cstdio> 
#include <algorithm>  
#include <cmath>  
#include <cstring>  
#include <map>  
using namespace std;

long long q_mul( long long a, long long b, long long mod ) //快速计算 (a*b) % mod
{
	long long ans = 0;	// 初始化
	while(b)				//根据b的每一位看加不加当前a
	{
		if(b & 1)			//如果当前位为1
		{
			b--;
			ans =(ans+ a)%mod;   //ans+=a
		}
		b /= 2;							//b向前移位
		a = (a + a) % mod;			//更新a

	}
	return ans;
}

long long q_pow( long long a, long long b, long long mod ) //快速计算 (a^b) % mod
{
	long long ans = 1; // 初始化
	while(b)//根据b的每一位看乘不乘当前a
	{
		if(b & 1)	//如果当前位为1
		{
			ans = q_mul( ans, a, mod ); //ans*=a
		}
		b /= 2;										//b向前移位
		a = q_mul( a, a, mod );			//更新a
	}
	return ans;
}


int main( )
{
	long long a, b, n;
	while(cin >> a >> b >> n)
	{
		cout << "a*b%n = " << q_mul( a, b, n ) << endl;
		cout << "a^b%n = " << q_pow( a, b, n ) << endl;
	}
	return 0;
}

好了，五一节就这么结束了，又要开学啦，，烦躁。

本文链接：https://blog.csdn.net/maxichu/article/details/45459715

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

合宙ESP32C3基于VSCode PIO Arduino开发框架初探教程_合宙esp32 c3更换flash-程序员宅基地

文章浏览阅读3.3k次，点赞3次，收藏43次。合宙ESP32C3基于VSCode PIO Arduino开发框架初探教程_合宙esp32 c3更换flash

Julia 并发编程 ---- @distributed 和 pmap的区别-程序员宅基地

文章浏览阅读1.2k次。目录1、功能说明2、代码用例2.1 使用 @distributed2.2 使用pmap3、总结1、功能说明@distributed（Julia 0.6之前用@parallel）会立即把要做的工作平均分配给所有的workers。注意，在@distributed中，会在指定范围在根据所有的worker的个数分片。相比之下，pmap将启动每个worker的工作，并根据w...

UE4如何检测目标在锥形视野内_unreal 计算目标是否在视锥体内-程序员宅基地

文章浏览阅读9.4k次，点赞5次，收藏15次。做UE4游戏AI方面经常会遇到一个问题，就是何如判定目标在AI单位的视野范围内，假如我们现在要检测玩家在AI单位的前方60°夹角的视野范围内，如果在的话就把玩家设置为该AI单位的目标。我做了一个简单的Service节点来处理，如图这两大图可能看不清，我把图分开又截了2张。当然这个简单节点中没有检测两者之间的距离，如果要实际应用肯定还要加..._unreal 计算目标是否在视锥体内

latex排版笔记_winedt 11-程序员宅基地

文章浏览阅读459次。latex写的格式不需要自己调，和编程差不多。关于latex和winedt的关系请参考百度：winedt 定义：　　WinEdt软件是一个Windows平台下的强大的通用文本编辑器，其更倾向于LaTeX/TeX文档的编辑　　latex定义：　　LaTeX（LATEX，音译“拉泰赫”）是一种基于ΤΕΧ的排版系统，由美国计算机学家莱斯利·兰伯特（Leslie Lamport）在20世纪80_winedt 11

TabLayout ViewPager fragment 联动_tablayout fragment绑定后如何联动 java android-程序员宅基地

文章浏览阅读245次。首先先看效果图:具体实现:首先导入依赖包:compile 'com.android.support:design:27.+'布局文件:<?xml version="1.0" encoding="utf-8"?><RelativeLayout ="http://schemas.android.com/apk/res/android" xmlns:..._tablayout fragment绑定后如何联动 java android

ffmpeg 编码生成mp4文件大小码率控制_ffmpeg保存mp4设置码率-程序员宅基地

文章浏览阅读1.2w次，点赞6次，收藏14次。AVCodecContext* pCodecCtx = m_stVideoStream.pStream->codec; JP_ASSERT(NULL != pCodecCtx); pCodecCtx->codec_id = eVideoCodecId; pCodecCtx->gop_size = 1_ffmpeg保存mp4设置码率