题解 | #剪绳子（进阶版）#
剪绳子（进阶版）
https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741
3作指数最好，不明白的看《剪绳子》中等题。
然后使用快速幂，时间复杂度O(logn)
注意大数越界问题。python可以不用考虑。
class Solution: def cutRope(self, n: int) -> int: if n <= 3: return n - 1 a = n // 3 - 1 # 快速幂的指数（已剥离余数3，4，5） b = n % 3 # 最后的余数：3，4，5对应乘3，乘2*2，乘3*2 d, res = 3, 1 # 以3为底 # 快速幂，不断翻倍基底d while a > 0: if a % 2: res = (res * d) % 998244353 d = d ** 2 % 998244353 a //= 2 if b == 0: return (res * 3) % 998244353 if b == 1: return (res * 4) % 998244353 return (res * 6) % 998244353
查看40道真题和解析
，太厉害了
投递牛客等公司10个岗位 >