高速乘法/幂 算法详解
快速乘法/幂 算法详解
好了，五一节就这么结束了，又要开学啦，，烦躁。
快速乘法/幂 算法详解
适用范围：快速计算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;
}
好了，五一节就这么结束了，又要开学啦，，烦躁。