描述

剑指offer JZ83 剪绳子（进阶版）
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]k[2]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

由于答案过大，请对 998244353 取模。

前置思路数学原理：

  1. 数学原理说明

图片截取于牛客题解官题解思路

​

方法一：快速幂法

思路：由于我们知道运算规则，只需要分三种情况：1.长度除以3余数为0。 2.长度除以3余数为1。 3.长度除以3余数为2.。三种情况分别求解即可。但是由于数字过大，如果直接用Math.pow()进行幂运算的话，会导致运超时。所以我们需要一个新的方法来进行幂运算。
快速幂运算原理：比如我们需要求3的5次幂，我们可以将5看作二进制数101，那么容易看出来，第几次位上有1，就代表3的几次幂，最后将各个位数的结果相乘得到最终结果。比如3的5次幂是243，我们使用快速幂法，101的第一位有1，得出1乘以3的1次幂；101第二位上为0，得出0
代码实现与相应解释说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    long mod = 998244353;
    public long cutRope (long number) {
    分三种情况讨论计算
        if (number <= 3) return number - 1;
        if (number % 3 == 0) {
            return fastx(3, number / 3);
        } 
        if (number % 3 == 2) {
            return fastx(3, number / 3) * 2 % mod;
        }
        else return fastx(3, number / 3 - 1) * 4 % mod;
    }
        /**
     * 快速幂法
     *
     * 代码逻辑见上文快速幂原理
     * @param x long 为底数， y long 为指数
     * @return long 为运算结果
     */
    long fastx(long x, long y) {
        long res = 1;
        while (y != 0) {
            if ((y & 1l) == 1) {
                res *= x;
                //每次取余防止数字过大
                res %= mod; 
        }
        x *= x;
        x %= mod;
        y >>= 1;
        }
        return res % mod;
}

}