企业官网建设流程全解析

慢速乘

在写程序进行乘法运算时，我们有时会遇到大数溢出的情况（比如两个101810^{18}1018的数相乘对1018+710^{18}+71018+7取模）。
这个时候我们就可以用慢速乘（你用__int128_t的话就可以不用管）。

一、原理

利用乘法分配律，将乘法转化为加法，通过二进制拆分其中一个乘数，边加边取模，避免溢出。

有一个数xxx，举个栗子，当xxx为131313时，它的二进制可写为110111011101：

13=23+22+20 13 = 2^3 + 2^2 + 2^013=23+22+20

那么：

a×13=a×23+a×22+a×20 a \times 13 = a \times 2^3 + a \times 2^2 + a \times 2^0a×13=a×23+a×22+a×20

计算时，不断将aaa加倍（相当于a×2ka \times 2^ka×2k），若xxx的当前二进制位为111，则累加当前的aaa。

二、代码实现（C++）

#defineintlonglongintmsc(inta,intb,intmod){intans=0;a%=mod,b%=mod;while(b){if(b&1)ans=(ans+a)%mod;b>>=1;a=a*2%mod;}returnans;}

三、复杂度

(O(log⁡b))(O(\log b))(O(logb))，比直接乘法慢，但能避免溢出。

快速幂

与慢速乘思想类似，但将乘法替换为乘方运算。

一、原理

计算abmod pa^b \mod pabmodp：

a13=a23×a22×a20 a^{13} = a^{2^3} \times a^{2^2} \times a^{2^0}a13=a23×a22×a20

二进制拆分指数，底数不断平方。

二、代码实现

#defineintlonglongintksm(inta,intb,intmod){intans=1;a%=mod,b%=mod;while(b){if(b&1)ans=msc(ans,a,mod);b>>=1;a=msc(a,a,mod);}returnans;}

三、复杂度

(O(log⁡b))(O(\log b))(O(logb))，高效。

对比总结

两者代码结构几乎一样，只是一个用+和+=，一个用*和*=。