快速幂/欧拉降幂

快速幂

• 介绍

  所谓快速幂就是在可以在 $ 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; 
  }
  

欧拉降幂