avatar

快速乘法

快速乘法

快速乘的名字是从快速幂抄过来的,事实上它比直接乘要慢。

思路和快速幂一样,对于 k×xk \times x ,可将其视为 k2×x+k2×x\frac{k}{2} \times x + \frac{k}{2} \times x ,若 kk 为奇数,则再加个 xx

1
2
3
4
5
6
7
int fastTimes(int x, int k, int p) {
if(k == 0) return 0;
int z = fastTimes(x, k >> 1, p);
z = (z + z) % p;
if(k % 2 == 1) z = (z + x) % p;
return z;
}
文章作者: Ender
文章链接: https://www.ender.xin/post/e012b153.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论