[Go]剑指offerJZ83 剪绳子（进阶版）-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

给你一根长度为 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 取模。

数据范围：2≤n≤10^14

进阶：空间复杂度 O(1)，时间复杂度 O(logn)

二、思路分析：

本题中是剪绳子的进一步拓展，在之前的剪绳子中，我们通过使用数学归纳的方式，将绳子尽可能切成n个长度为3的段。由于指数增长快，因此得到的乘积也大。具体可回顾[Go]剑指offerJZ14 剪绳子

之前是绳子长度数据范围n不到60，想要计算出3的n次幂并不算太难，在O(n)的时间范围内完成计算并不会相差太多。但是，本题绳子长度范围急剧扩大，随着数据增大会面临两个问题：

复杂度随数据增大而线性增长；
乘积爆炸增长，后续每次计算都存在越界的可能。

之前数学归纳的方法，实际上已经没有继续提高的空间了，此步骤中，时间复杂度已经为O(1)。我们需要进行修改的是计算幂次时的时间消耗：使用连乘需要进行n次计算，而使用快速幂只需要使用logn次计算即可完成，但是这又带来了新的问题——快速幂需要递归进行实现，因此需要维护O(logn)的栈空间，不符合题目O(1)的空间复杂度要求。

因此还需要继续改进，可将快速幂通过二进制计算进行实现，在之前的文章中也有介绍，这里就不多加赘述了：

[Go]剑指offerJZ16 数值的整数次方

最后，只需要注意别让数据越界，在每次数据相乘后都需要进行一次取余操作即可。

三、AC 代码：

代码部分直接将两次解题进行了一个整合即可得到符合题目要求的答案：

func cutRope( number int64 ) int64 {
    // write code here
    if number == 2 {
        return 1
    }
    if number == 3 {
        return 2
    }
    var threeNum int64 = number / 3
    
    if number % 3 == 0 {
        return Power(3, threeNum) % 998244353
    }
    if number % 3 == 1 {
        threeNum--
        return 4 * Power(3, threeNum) % 998244353
    }
    return 2 * Power(3, threeNum) % 998244353
}

func Power(base int64, exponent int64) int64 {
    // write code here
    var ans int64 = 1
    x := base
    for exponent != 0 {
        if exponent & 0x01 != 0 {
            ans = ans * x % 998244353
        }
        x = x * x % 998244353
        exponent >>= 1
    }
    return ans
}
复制代码