【解题报告】《算法零基础100讲》(第15讲) 二分快速幂 - Java

• 零、相关知识
• • 1.快速幂
  • 2.欧拉函数 及 欧拉降幂公式
  • • 2.1.欧拉函数
    • 2.2.欧拉降幂公式
• 一、50. Pow(x, n)
• • 1.题目
  • 2.分析
  • 3.代码
• 二、372. 超级次方
• • 1.题目
  • 2.分析
  • 3.代码

• 我一开始听到快速幂，不知道这是做什么用的，就去先自己了解了一下，也在这里简单做一个记录，有错漏的地方欢迎指正。
• 快速幂计算： a b   m o d   c a^b mod c ab mod c
• 在很多地方都能使用到快速幂，比如说RSA加密算法，需要用到： ( 明 文 ) e   m o d   n   和   ( 密 文 ) d   m o d   n (明文)^e mod n 和 (密文)^d mod n (明文)e mod n 和 (密文)d mod n，下面通过一个例子来引入快速幂
• 例子：5⁵ mod 7
  （1）简单的，可以直接 5×5×5×5×5 mod 7，这里的4步幂次计算，时间复杂度近似为 O ( N ) O_{(N)} O(N)​。这里幂次比较小还好，但是一般幂次都会比较大，这样耗时就会比较长。
  （2）如果通过二分法做一个降幂的优化，如下图所示：
  
  （3）将 5 5 5^5 55 的幂次除以2，因为指数是奇数，所以还需要乘 5 1 5^1 51 ，得到 5 2 × 5 2 × 5 1 5^2×5^2×5^1 52×52×51。继续降幂， 5 2 5^2 52 又可以分为 5 1 × 5 1 5^1×5^1 51×51，最后得到的就是： ( 5 2 ) 2 × 5 (5^2)^2×5 (52)2×5，这里的运算总共就是3步，相较于上一种方法运算步骤要少了。
  （4）虽然在这里看起来还是差不多，但是当幂次大了之后，两者的区别就会显现出来。
• 例如：计算 5 16 5^{16} 516
  （1）如果是直接乘，就需要乘（16 - 1）=15次；
  （2）如果用二分快速幂，就是 ( ( ( 5 2 ) 2 ) 2 ) 2 (((5^2)^2)^2)^2 (((52)2)2)2，总共4步运算，时间复杂度近似为 O ( l o g 2 N ) O_{(log_2N)} O(log2​N)​，区别就很显而易见了。
• 最后总结一下二分快速幂，需要分为三种情况来计算：
  

欧拉函数 以及 欧拉降幂公式 在第二题有用上，所以得去自学了才能回来做这道题，这里把自学做的笔记贴一下供大家参考~

a b ≡ { a b % φ ( n ) (   m o d     n )                    n , a 互 质 a b (   m o d     n )                          b < φ ( n ) a b % φ ( n ) + φ ( n ) (   m o d     n )          b ≥ φ ( n ) a^bequiv left{ begin{aligned} a^{b%varphi(n)}(bmod n) n,a互质\a^b (bmod n) b

具体的证明过程：https://blog.csdn.net/weixin_38686780/article/details/81272848

看不懂的记下公式即可。

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
-10⁴ <= xⁿ <= 10⁴

这里涉及到的知识点：

1. 幂运算： a − b = 1 a b a^{-b}=frac{1}{a^b} a−b=ab1​
2. 模运算的特点： n % p n % p n%p 得到结果的正负由被除数 n n n 决定,与 p p p 无关。
   即： 7 % 3 = 1 ; 7 % ( − 3 ) = 1 ; ( − 7 ) % 3 = − 1 ; ( − 7 ) % ( − 3 ) = − 1 ; 7 % 3 = 1;7 % (-3) = 1;(-7) % 3 = -1;(-7) % (-3) = -1; 7%3=1;7%(−3)=1;(−7)%3=−1;(−7)%(−3)=−1;
3. 二分快速幂（具体请往上滑）

思路：

1. 因为这道题的指数有可能是负数，所以需要把负数的情况也考虑进去。
2. 判断 n 是正数还是负数，如果是正数，则返回 x n x^n xn，否则返回 1 x n frac{1}{x^n} xn1​
3. 快速幂用的是递归的思路，递归的终点分别是 0 / 1 / -1。
4. 当 n == 0，返回 1
5. 当 n == 1 或 n == -1，返回 x

    public double myPow(double x, int n) {
        return n > 0 ? quickPow(x, n) : 1 / quickPow(x, n);
    }

    private double quickPow(double x,int n){
        if (n == 1 || n == -1){
            return x;
        }
        if (n == 0){
            return 1;
        }
        double t = quickPow(x, n / 2);
        //指数是否为偶数
        //正负数都一样
        return n % 2 == 0 ? t * t : t * t * x;
    }

372. 超级次方

计算 a^b 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
1 <= a <= 2³¹ - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

因为这道题的指数非常大，所以首先想到的，就是一边降幂一边取模，否则很容易就溢出。

这道题涉及到的知识点：

1. 模运算规则： ( a ∗ b ) % p = ( a % p ∗ b % p ) % p (a * b) % p = (a % p * b % p) % p (a∗b)%p=(a%p∗b%p)%p
2. 欧拉函数： φ ( N ) = N ( 1 − 1 p ) ( 1 − 1 q ) varphi(N)=N(1-frac{1}{p})(1-frac{1}{q}) φ(N)=N(1−p1​)(1−q1​)
3. 欧拉降幂公式： a b   m o d   n = a b % φ ( n ) + φ ( n )   m o d     n a^b mod n=a^{b%varphi(n)+varphi(n)}bmod n ab mod n=ab%φ(n)+φ(n)mod n

思路：

1. 欧拉函数代码实现
   基于欧拉降幂公式用到了 φ ( N ) varphi(N) φ(N)，所以需要将欧拉函数进行代码实现，再把1337代入求出结果 φ ( 1337 ) varphi(1337) φ(1337)。
   又因为在运算中需要整数运算，所以不能直接套用上方公式的 N ( 1 − 1 p ) N(1-frac{1}{p}) N(1−p1​)，需要进行化简：
   N ( 1 − 1 p ) 抽 取 1 p 得 ： N p ( p − 1 ) N(1-frac{1}{p})抽取frac{1}{p}得：frac{N}{p}(p-1) N(1−p1​)抽取p1​得：pN​(p−1)
   实现步骤：
   （1）分解质因数
   （2）分解质因数的过程中代入上述公式求出欧拉函数
   （3）因为遍历循环范围为 [ 2 , N ] [2,sqrt N ] [2,N ​]，有可能出现遍历完还剩下质因子为遍历到的情况，需要单独处理。
   具体实现：

    //欧拉函数
    private int euler(int n) {
        int i,res = n;
        for (i = 2;i * i < n;i++){
            if (n % i == 0){
                //欧拉函数
                res = res / i * (i - 1);
                //除完该质因子
                do {
                    n /= i;
                } while (n % i == 0);
            }
        }
        if (n > 1){
            res = res / n * (n - 1);
        }
        return res;
    }

2. 得到 φ ( N ) varphi(N) φ(N)后，遍历指数数组 int[] b 并计算欧拉降幂公式中 b % φ ( n ) + φ ( n ) b%varphi(n)+varphi(n) b%φ(n)+φ(n)的值。
3. 最后通过二分快速幂的方法，结合模运算的性质计算出结果并返回。

    public int superPow(int a, int[] b) {
        //欧拉函数
        int c = euler(1337);
        //k%φ(m)+φ(m)
        int k = 0;
        for (int i : b) {
            k = (k * 10 + i) % c;
        }
        k += c;
        return (int)binPow((long)a, k, 1337);
    }

    //欧拉函数
    private int euler(int n) {
        int i,res = n;
        for (i = 2;i * i < n;i++){
            if (n % i == 0){
                //欧拉函数
                res = res / i * (i - 1);
                //把该质因子除完为止
                do {
                    n /= i;
                } while (n % i == 0);
            }
        }
        if (n > 1){
            res = res / n * (n - 1);
        }
        return res;
    }

    
    private long binPow(long a,int b,int p){
        if (b == 0){
            return 1;
        }
        a %= p;
        long t = binPow(a, b / 2, p);
        return b % 2 == 0 ? t * t % p : t * t % p * a % p;
    }