参考链接：
相乘取模（快速模）
快速乘 + 快速幂 + 取模
我们需要解决的问题是计算出
a * b mod p
。
按照普通的算法，只需一行即可。但有的时候a与b的规模很大，达到10
18
，相乘就会溢出。而结果往往只要求取模。那么我们便需要相乘取模。
参考快速幂的想法，我们同样可以把b拆为一个二进制数。
首先我们可以将指数b转换为一个二进制数。
例如b=9，对应的二进制数为1001。那么我们可以得到
9
=
1
∗
2
3
+
0
∗
2
2
+
0
∗
2
1
+
1
∗
2
0
9=1*2^3+0*2^2+0*2^1+1*2^0
9
=
1
∗
2
3
+
0
∗
2
2
+
0
∗
2
1
+
1
∗
2
0
那么便可以得出性质1：
a
∗
9
=
a
∗
(
2
3
+
2
0
)
a*9=a*(2^3+2^0)
a
∗
9
=
a
∗
(
2
3
+
2
0
)
根据这个性质我们便可以做快速乘和快速模乘了。
对于快速乘来说。
我们用
ans
记录当前的答案，用
b & 1
判断当前位为1，还是为0。
根据性质1我们可以知道，如果当前我们推到的二进制数的位数上是1（例如9转换为二进制数后的第0位和第3位），那么
ans = ans + a * 2
，否则
ans
不用更新。
而无论
ans
是否更新，
a
和
b
都需要继续判断下一步（即需要更新）。
其中，
b
需要判断高一位是否为1（即右移一位），
a
需要往前进一位（即左移一位，2
0
->2
1
）。
//快速乘法：计算a*b
public static int qmul_num(int a, int b) {
int ans = 0;
while (b != 0) {
if ((b & 1) != 0) {
ans += a;
}
b >>= 1;
a <<= 1;
}
return ans;
}
快速模乘就是比快速乘多了取模这一步。
//快速乘法 + 取模
public static int qmul_mod(int a, int b, int mod) {
int ans = 0;
while (b != 0) {
if (((b %= mod) & 1) != 0) {
ans += a %= mod;
}
b >>= 1;
a <<= 1;
}
return ans % mod;
}