c++ 快速乘
发布日期:2021-06-21 02:54:47 浏览次数:6 分类:技术文章

本文共 574 字,大约阅读时间需要 1 分钟。

First

在一些数学题中,两个数相乘运算很多,同时又很容易溢出,如两个 long long 相乘

今天本蒟蒻来总结一下快速乘的两种方法

1:二进制

和快速幂的原理一样,优化一个一个加的算法,复杂度\(O(\log n)\)

适用于一般场合,慢但是稳定

typedef long long LL;inline LL Mul(LL x,LL y,LL p){	register LL res=0;	for(;y;y>>=1,x=(x+x)%p)	if(y&1)res=(res+x)%p;	return res;}

2:运用 Long Double

原理:\(a\times b\mod p=a\times b-\lfloor\dfrac{a\times b}{p}\rfloor\times p\)

就是利用long double处理\(\lfloor\dfrac{a\times b}{p}\rfloor\),复杂度\(O(1)\)
适用于需要卡常数的题目,但是long double有精度问题,若数据太大容易出锅

typedef long long LL;typedef long double LD;inline LL Mul(LL x,LL y,LL p) {    return (x*y-(LL)((LD)x/p*y)*p+p)%p;}

转载地址:https://blog.csdn.net/KonjakuLAF/article/details/115714550 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:c++ FHQ Treap
下一篇:2020 CSP-J 初赛游记

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年04月17日 08时57分41秒