【例题】64位整数乘法

题目地址

  • 方法一 (口胡一下就好了啊)

快速幂思想的灵活运用。

\(b\) 用二进制表示 , 设 \(b\) 在二进制下有 \(k\) 位 , \(c_i\) 表示 \(b\) 在二进制下的第 \(i\)

\[b=c_{k-1}*2^{k-1}+c_{k-2}*2^{k-2}+...+c_{0}*2^{0}\]

根据加法原理,\(a*b\) 相当于 \(b\)\(a\) 相加,现在把 \(b\) 用二进制表示,那么就有:

\[a*b=c_{k-1}*2^{k-1}*a+c_{k-2}*2^{k-2}*a...+c_0*2^0*a\]

根据模运算的规则,边运算边取模。

再打上类似快速幂的板子,就可以分分钟切掉这题了。这里不放代码,因为我没写。

  • 方法二 (玄学方法)

我们知道:

\[a*b \text{ mod } p = a*b-[\frac{a*b}{p}]*p\]

注:[ ]暂且看做向下取整

然后书中用了 long double 胡搞一下就过了。反正我是没看懂。

有兴趣的朋友可以写一下。

咱也不知道,咱也不敢问,咱也不想问。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:17
听说过付费实习,没想到这么贵啊我去,要不我给你个腰子吧
哈哈哈,你是老六:这种公司一定要注意啊,不要随便签合同,只要签了后面钱可能回不来,而且你通过法律途径也弄不回
点赞 评论 收藏
分享
猫头夜鹰:图书管理系统能有面试就怪了,放十年前都不行
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务