当前位置:首页 > C++知识 > 正文内容

【数论】快速乘

亿万年的星光3年前 (2023-02-04)C++知识19241

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

快速乘的原理和龟速乘不同,快速乘并不是基于二进制和位运算,严格来说,快速乘是利用了一个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)保证了它们溢出后的差值基本不变,所以即使它会溢出也不会影响最终结果的!


优点与缺点:

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

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:【数论】龟速乘

下一篇:unsigned

相关文章

【数论】龟速乘

【数论】龟速乘

我们前面一篇文章学习了快速幂。它可以解决两类问题:a^b,(a^b)%c对于第一类,我们可以使用递归法或者迭代法可以求出,为了计算的快,我们可以引入位运算操作,但是目前来看,无论怎么优化都不能超过lo...

第十四届全国青少年信息学奥林匹克联赛初赛试题(NOIP2008年普及组初赛C++试题及参考答案)

第十四届全国青少年信息学奥林匹克联赛初赛试题(NOIP2008年普及组初赛C++试题及参考答案)

第十四届全国青少年信息学奥林匹克联赛初赛试题             ...

树的遍历

在应用树结构解决问题时,往往要求按照某种此项获得树中全部结点的信息,这种操作叫做树的遍历。遍历的方法有很多种。常用的有:A. 先序遍历:先访问根结点,再从左到右按照先序思想遍历各子树。B. 后序遍历:...

【STL】二分查找函数 lower_bound 和 upper_bound

一、 lower_bound【功能】在数组a中从a[begin]开始到a[end - 1]按照cmp函数来比较进行二分查找第一个大于等于k的数的地址,如果有第一个大于等于k的数则返回该数的地...

【贪心】区间选点

【贪心】区间选点

【题目描述】数轴上有n个闭区间[ai, bi],取尽量少的点,使得每个区间内都至少有一个点。(不同区间内含的点可以是同一个,1<=n<=10000,1<=ai<=bi<=...

分离整数的各个位

分离整数的各个位

        平常做题的时候有很多时候会遇到分离整数的各个位的操作,比如求回文数,数字反转等题目。今天简单总结一下分离...