快速乘

16年北京网络赛遇到了这个技巧…但是竟然忘记记了下来?

快速乘是为了解决 计算ab % mod 时ab溢出LL 的问题

比如a=1E16,b=1E16,mod=1E18,虽然最后的结果没有溢出,但是中间溢出了。

原理和快速幂很类似,具体可以参考 晴川大爷的专栏

完全就是把快速幂中的乘法变成加法了嘛(从记忆角度考虑orz

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz