【例题】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 胡搞一下就过了。反正我是没看懂。

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

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