快速幂

• 介绍

  所谓快速幂就是在可以在 $ O(\log{k})$ 的时间复杂度内求得\(x^k\ \ mod\ \ p\)的结果。

  我们知道常规的算法求幂需要 \(O(k)\)的复杂度。

  int res = 1;
  for(int i = 1; i <= k; i++)
  {
      res = res * a mod p;
  }
  

• 核心思想：反复平方

  首先，我们都知道任意一个十进制的数k都可以转换为\(2^{i_1}+2^{i_2}+2^{i_3}+...+2^{i_t}\)这样的形式。

  那么\(a^k\) 一定可以写成 \(a^{2^{i_1}+2^{i_2}+2^{i_3}+...+2^{i_t}}\)这样的形式。

  进而求解\(a^k \ \% \ p\) 实际上就是求\((a^{2^{i_1}+2^{i_2}+2^{i_3}+...+2^{i_t}} )\% \ p\)。

  又由取模运算规则：

  \[(a+b)\%p = (a\%p + b\%P)\%p\\(a-b)\%p = (a\%p - b\%P)\%p\\(a*b)\%p = (a\%p * b\%P)\%p\\a^b \ \% \ p = ((a \% p)\ ^b)\ \% \ p \\....\\
  \]

  \((a^{2^{i_1}+2^{i_2}+2^{i_3}+...+2^{i_t}} )\% \ p = (a^{2^{i_1}} * a^{2^{i_2}} *a^{2^{i_3}} *a^{2^{i_t}}) \% \ p = ..\)

  利用乘法的模运算规则，迭代即可。

  所以关键的问题就是把k转换为\(2^{i_1}+2^{i_2}+2^{i_3}+...+2^{i_t}\)这样的形式。

  关于代码：一共迭代\(\log{k}\)次

  \[a^{2^0} \quad mod \quad p\\
  a^{2^1} \quad mod \quad p\\
  a^{2^2} \quad mod \quad p\\
  a^{2^3} \quad mod \quad p\\
  a^{2^4} \quad mod \quad p\\
  .\\
  .\\
  a^{2^{\log{k}}} \quad mod \quad p
  \]

  其中显然可知：\(a^{2^{i+1}}\) = \(a^{2^{i} * 2}\) = \(({a^{2^{i}}})^2\)

  代码模板

  //a^k mod p
  int qmi(int a,int k, int p)
  {
      int res = 1;
      while(k)
      {
          if(k & 1) res = (LL)res * a % p;
          k >> 1;
          a = (LL)a * a % p;
      }
      return res; 
  }
  

欧拉降幂