慢速乘与快速幂

慢速乘在写程序进行乘法运算时我们有时会遇到大数溢出的情况比如两个101810^{18}1018的数相乘对1018710^{18}710187取模。这个时候我们就可以用慢速乘你用__int128_t的话就可以不用管。一、原理利用乘法分配律将乘法转化为加法通过二进制拆分其中一个乘数边加边取模避免溢出。有一个数xxx举个栗子当xxx为131313时它的二进制可写为11011101110113232220 13 2^3 2^2 2^013232220那么a×13a×23a×22a×20 a \times 13 a \times 2^3 a \times 2^2 a \times 2^0a×13a×23a×22a×20计算时不断将aaa加倍相当于a×2ka \times 2^ka×2k若xxx的当前二进制位为111则累加当前的aaa。二、代码实现C#defineintlonglongintmsc(inta,intb,intmod){intans0;a%mod,b%mod;while(b){if(b1)ans(ansa)%mod;b1;aa*2%mod;}returnans;}三、复杂度(O(log⁡b))(O(\log b))(O(logb))比直接乘法慢但能避免溢出。快速幂与慢速乘思想类似但将乘法替换为乘方运算。一、原理计算abmod pa^b \mod pabmodpa13a23×a22×a20 a^{13} a^{2^3} \times a^{2^2} \times a^{2^0}a13a23×a22×a20二进制拆分指数底数不断平方。二、代码实现#defineintlonglongintksm(inta,intb,intmod){intans1;a%mod,b%mod;while(b){if(b1)ansmsc(ans,a,mod);b1;amsc(a,a,mod);}returnans;}三、复杂度(O(log⁡b))(O(\log b))(O(logb))高效。对比总结方法操作作用复杂度慢速乘加法代替乘法防止乘法溢出(O(\log b)$快速幂乘法代替乘方快速求幂(O(\log b)$两者代码结构几乎一样只是一个用和一个用*和*。