【数论】快速乘
上一篇文章简单说了龟速乘的问题，有人觉得龟速乘还是太慢了，有没有什么办法再快一点，实际是有的，就是我们今天介绍的 快速乘。
快速乘的原理和龟速乘不同，快速乘并不是基于二进制和位运算，严格来说，快速乘是利用了一个bug才实现的功能。
这个bug 就是 long double 和long long 的定义范围不同。因为long double的范围比long long 大一些。
它来源于下面这篇文章：
什么意思呢？
简单来说，就是就是在原地爆炸的边缘疯狂试探，把本来存进long long会炸掉的值先进行计算，用long double暂时存下，然后再把差值——一个不会超过long long的数字塞回去，再特判一下精度问题，就大功告成了。
int QuickMult(long long a,long long b,long long mod) {
long long d=(long double)a/mod*b;
long long ans=(unsigned long long)a*b-(unsigned long long)d*p;
return (ans+mod)%mod;
}但是它就是可以算出正确答案来。因为它其实很巧妙的运用了自动溢出这个操作，我们的代码中的z就表示 所以我们要求的就变成了 ，虽然这两个部分都是会溢出的，但（unsigned）保证了它们溢出后的差值基本不变，所以即使它会溢出也不会影响最终结果的！
优点与缺点:
优点就是代码简短高效，缺点就是容易丢失精度。
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。