模运算与快速幂算法

最近的日常学习又涉及到了不少和 mod 有关的计算,这些计算虽然都不是很难,但有的还是需要一点点小技巧。
忖,遂记之。

模运算公式


快速幂算法

上面那堆公式里,有一行红色公式就是这里的主角了,可以用它来快速计算 $ a^b \;\%\; p$ 的结果。

直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unsigned long func(unsigned long a, unsigned long b, unsigned long p) {

unsigned long result = 1;

while (b) {

if (b & 1)
result = (result * a) % p;
b >>= 1;
a = (a * a) % p;
}

return result;
}

代码比较简单,也很直观,就不多做解释了。

------本文结束感谢您的阅读 ------
0%