分治算法——快速幂



分治算法——快速幂

（我貌似不会写二进制拆分的快速幂。。。。）

对于求解a^b mod p，我们的暴力手段是模拟，将b个a一个一个乘上去再取模

时间显然是O（b）,当b有几千万，乃至几亿时，我们发现这显然会超时

思考有没有优化的空间呢

我们发现求解a^b mod p 等价于下面的问题：


(a^2)  ^  (b/2) mod p （当b为偶数时）

(a^2)  ^ (b div 2) * a mod p （当b为奇数时）

我们显然可以将这个求解 a^b mod p这个原问题，转化为上述与原问题结构相同，但是规模更小的子问题来解决（这显然是一个分治）

我们不妨用ans表示问题的答案，同时当问题分离出一个a时，我们就直接将其乘入ans中

通过不断的递归，当b为0时可以直接出解了，由于每一次对于原问题将其分解都会使得b/2，则会发现其时间复杂度为O(lg b)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var
b,p,k,ans,x,y,z:longint;
begin
  readln(b,p,k);
  x:=b; y:=p; z:=k;
  ans:=1; b:=b mod k;
  while p<>0 do
  begin
    if p and 1=1 then ans:=ans*b mod k //p是否为奇数
    else ans:=ans mod k;
    b:=(b*b) mod k; //每一次分解都会使得b变为b^2
    p:=p>>1;  //p减少了一般
  end;
  writeln(x,'^',y,' mod ',z,'=',ans mod k);
end.、
//不写递归的原因是递归比较慢