编程 取余运算
发布网友
发布时间：2022-05-20 13:00
共1个回答
热心网友
时间：2023-10-22 07:21
for i:=1 to p do
b:=(b mod k)*b mod k;
现在p比较大，所以将p用二进制表示以寻求优化,设p=2^k0+2^k1....
则算法可化为：
for i:=1 to 2^k0 do ....
for i:=1 to 2^k1 do .....
....
现在要计算的是p^(2^k0+2^k1....) mod k
即p^2^(k0+k1+....) mod k
所以算法可化为：
(将p传化成2进制数放在binary数组中)
rest:=b;
for i:=1 to len do
if binary[i]=1 then
for j:=1 to i do rest:=(rest mod k)*(rest mod k) mod k;
该算法的时间复杂度为O((log2(n))^2)，已经可以解决题目的问题
不过要继续优化也是可以的
我们观察上面的算法，可以发现
若k0>k1,那么在计算p^2^k0中已经计算了p^2^k1
所以j的循环是可以放入i循环中的
再经过优化后，算法就变成了下面的样子，就是你上面的程序：
rest:=1;
for i:=len downto 1 do begin
temp:=rest*rest mod k;
if binary[i]=1 then
rest:=(b mod k*temp) mod k
else rest:=temp;
end;
算法可以这样理解：
比如现在要计算p^2^(m+n0)
设当前计算到了二进制数p的第m位，即i=len-m+1，且binary[m]=1,之前已经计算了b^2^n1
(就相当于要计算b^2^m)
现在将b^2^n1乘上b，就变成b^2^n1*b
这样在接下来的循环中，还要再循环m次，循环结束后就变成了(b^2^n1*b)^2^m
即p^2^(m+n0)
这样就满足了原来的要求
说得不是很清楚，请见谅
