快速幂取模算法

2019-04-13 13:27发布

站内文章 / 模拟电子
15489 0 1424
原文地址：https://blog.qjm253.cn/?p=369

问题需求

求 ab % c, 其中a，b的值可能很大，导致 ab 的值long long都存不下

预备知识

  • 模运算的性质：(a · b) mod c = [ (a mod c) · (b mod c) ] mod c
  • · => 点乘，在这里就是指普通乘法云算法

实现思路

对于 ab % c
1. 首先我们将b分解成如下表示 b = b0 + b1 * 21 + ··· + bn * 2n (其中的 b0, b1, ···, bn 指的是对应b的二进制表示法中对应位置的取值，1或者0) => 比如：6 —> 110 => b0 = 0, b1 = 1, b2 = 1
  1. 则 ab 可以表示成下面的形式 ab = ab0 * ab1 * 21 * ··· * abn * 2n => 令 ai = abi * 2i => 则：ab = a0 * a1 * ··· * an
  2. 运用上面提到的关于幂运算的性质 -> (a · b) mod c = [ (a mod c) · (b mod c) ] mod c 则 ab % c = ( (a0 % c) * (a1 % c) * ··· * (an % c ) ) % c

算法实现

int quickMod(int a, int b, int c){ int ans = 1; a = a % c; //所有项里面都有a，提取出来可统一先取模一下，减少计算量, 也可不加 while(b != 0){ if(b & 1) ans = (ans * a) % c; b >>= 1; a = (a * a) % c; } return ans; }

热门文章