描述
给你一根长度为 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 < = 节点值 < = 1 0 14 2<=节点值<=10^{14} 2<=节点值<=1014
进阶：空间复杂度 O(1) ， 时间复杂度 O(logn)
示例1
输入：4
返回值：4
说明：
拆分成 2 个长度为 2 的绳子，2 * 2 = 4
示例2
输入：5
返回值：6
说明：剪成一个长度为 2 的绳子和一个长度为 3 的绳子，答案为2*3=6
示例3
输入：874520
返回值：908070737
package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 原动态规划计算量太大 考虑使用快速幂（借助贪心思想）* 快速幂 相当于 二分 复杂度O(log2(n))* @param number long长整型* @return long长整型*/func cutRope(n int64) int64 {// write code hereif n <= 3 {return n - 1}mod := int64(998244353)if n%3 == 0 {return fastPow(3, n/3, mod) // 余数为0 所有段长为3} else if n%3 == 1 { // 余数为1 最后一个段长为1 将长度为3的段+1 保留一个长度为4的段return (fastPow(3, (n/3)-1, mod) << 2) % mod} else { // 余数为2return (fastPow(3, n/3, mod) << 1) % mod}
}// base^exp mod Mod
func fastPow(base, exp, mod int64) int64 {res := int64(1)for exp > 0 {if exp%2 == 1 {res = (res * base) % mod}base = (base * base) % modexp /= 2}return res
}
