快速幂与快速乘

发表于 | 分类于

简单的二进制应用

快速幂

在程序设计竞赛中，快速幂的应用十分广泛，它可以在$\Theta(logn)$的时间内计算$a^n$的值。

该算法基于这样的事实： $a^{b+c}=a^b*a^c$。所以在计算$a^n$时可以把$n$转为二进制并拆分为若干个2的幂次项的和。以$3^6$为例：

\[3^6 = 3^{(110)_2} = 3^{2^2+2^1} = 3^{2^2}*3^{2^1}\]

由于等式右边最多拆分为$logn$项的积，故时间复杂度为$\Theta(logn)$。在矩阵运算中，例如斐波那契数列求若干项的值，矩阵连乘也可以用快速幂的思想加快运算。

代码

1
2
3
4
5
6
7
8
9
ll ksm(ll a, ll b, ll mod){
	ll res = 1;
	while(b){
		if(b&1) res = res*a%mod;
		a = (a*a)%mod;
		b >>= 1;
	}
	return res%mod;
}

注意最终结果要进行一次取模，否则当$b,mod=0,1$时会出错。

快速乘

快速乘可以用于两个64bit数相乘爆精度的问题，但实际上却没怎么碰到过，第一次用到它居然是数字逻辑考试的一道$verilog$分析题。

该算法可以在$\Theta(logb)$时间内计算$ab$的值，和快速幂很相似，主要思想基于$a(b+c)=ab+ac$，以5*11为例：

\[5*11=5*(1011)_2 = 5*(2^3+2^1+2^0) = 5*2^3+5*2^1+5*2^0\]

代码

1
2
3
4
5
6
7
8
9
ll ksc(ll a, ll b, ll mod){
	ll res = 0;
	while(b){
		if(b&1) res = (res+a)%mod;
		a = a*2%mod;
		b >>= 1;
	}
	return res;
}