上一篇文章简单说了龟速乘的问题，有人觉得龟速乘还是太慢了，有没有什么办法再快一点，实际是有的，就是我们今天介绍的 快速乘。

快速乘的原理和龟速乘不同，快速乘并不是基于二进制和位运算，严格来说，快速乘是利用了一个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就表示 ⌊x×y/p⌋所以我们要求的就变成了 x×y−⌊x×y/p⌋×p，虽然这两个部分都是会溢出的，但（unsigned）保证了它们溢出后的差值基本不变，所以即使它会溢出也不会影响最终结果的！

优点与缺点:

优点就是代码简短高效，缺点就是容易丢失精度。

(adsbygoogle = window.adsbygoogle || []).push({});