算法竞赛进阶指南

• $a^b\%p$

  (快速幂) O(logb)

  时间复杂度分析：每次对b进行右移操作
  (a b ) % p = ((a % p ) (b % p) ) % p ; (a + b ) % p = ((a % p ) + (b % p) ) % p ;
  证明仅以a b % p；
  a = c1 p + d1 ; b = c2 p + d2;
  (a b) % p = (c1 p + d1 ) (c2 p+ d2 ) % p = (d1d2)%p;

  本题逻辑核心！！

  b可以拆成2的幂次方

  $b = C_{k}2^{k}C_{k-1}2^{k-1}….C_{1}2^{1}*C_{0}2^{0}$
  所以对于(a^b)%p式子的展开

  $a^{b} = a^{C_{k}2^{k}}*a^{C_{k-1}2^{k-1}}…a^{C_{0}2^{0}}$

  $1a^{C_{0}2^{0}}\%p = ((1\%p) (a^{C_{1}2^{1}}\%p) \% p)$

  $a^{b}\%p = ((1a^{C_{0}2^{0}})\%p (a^{C_{1}2^{1}}\%p)\%p……$

  a(x1)a(x2)%p) (a(x3)%p) ) %p

      1*a(x1)*a(x2)%p = ( (1*a(x1)%p) * (a(x2)%p) )%p
      1*a(x1)%p = ( (1%p) * (a(x1)%p) )%p
      所以res初始化值为1%p
      算法即是从下向上实现 
  2.理解a = a *a % p
      迭代a： ( res * (a(xn)%p) )%p 其中的a(xn)%p = a(xn-1)*a(xn-1)%p