数论 大数相乘的快速乘技巧
1.1 问题
快速乘常用于解决如下问题:long long 与 long long 相乘，对long long 取模。显而易见，结果有可能不在long long 范围内，可能会溢出。因此，我们需要一种对该问题的有效解决方法
2.1 __int128
玄学数据类型，联赛是肯定不能使用的，所以，弃疗(≧∇≦)ﾉ
2.2 龟速乘
快速幂的思路在于二进制优化一下乘法的过程，实现快速求幂；龟速乘的思路很接近，利用二进制优化一下加法的过程，实现龟速乘法。long long 相加总不会爆long long 吧<(￣ c￣)y▂ξ
ll qsc(ll a,ll b,ll m){
ll ans=0,base=a,mod=m;
while(b){
if(b&1) ans=(ans+base)%mod;
base=(base+base)%mod;
b>>=1;
}
return ans;
}
2.3 神奇小技巧
\[ull \Rightarrow unsigned long long \quad \quad \quad ld\Rightarrow long double
\]
\]
inline ull qsc(ll a,ll b,ll m){
ll z=(ld)a/m*b;
ll res=(ull)a*b-(ull)z*m;
return (res+m)%m;
}
实际上就是把取模的过程分解了一下
\[a\times b \mod p\equiv a\times b -\lfloor \frac {a\times b}{p}\rfloor \times p \mod p
\]
\]
用一下long double处理一下分数，然后再利用unsigned long long 对\(2^{64}\)智能溢出，实现了这个O(1)快速乘。虽然看上去不靠谱，但实际实验一下发现还的确是有正确性的。
原文链接: https://www.cnblogs.com/ticmis/p/13210665.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360310
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
