题解 | #剪绳子（进阶版）难点不在快速幂

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number long长整型 
# @return long长整型
#
class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        if number <= 3:
            return number-1
        elif number == 4:
            return 4
        else:
            if number%3 == 1:
                seg_n = (number-4)//3  #3x1<4, 所以当余数为1 时，把1和其中的一个3组合在一起作为因子，而不是把1和3分开作为两个因子
                return 4*self.quickPow(3, seg_n) % 998244353
            elif number%3 == 2:
                seg_n = (number-2)//3  #3x2>5, 所以把2,3作为两个因子
                return 2*self.quickPow(3, seg_n) % 998244353
            else:
                seg_n = number//3
                return self.quickPow(3, seg_n) % 998244353

    def quickPow(self, nums: int, seg_n: int):
        var_segn = seg_n * 1
        ret = nums * 1
        ret2 = 1
        while var_segn > 1:
            # print(ret)
            if var_segn%2:
                ret2 = ret2 * ret % 998244353
            var_segn = var_segn // 2
            ret = ret ** 2 % 998244353
        return ret*ret2

快速幂都能想到，这个题的难点也不在快速幂

1. 难点1-x**(1/x)的最小值，此题要穷举所有可能的分段大小根本不可能，所以必须先求出最小值。官解给出了结论：e，round取整为3。
2. 难点2-考虑到每个段的大小为整数，那就要考虑绳长不为3整数的情况，即余数为1或者2。注意，直接把最后分出去的一段长设为余数并不一定是最大值，需要讨论余数和3组合的情况，余数1需要和前面的一个3组合，余数2则不用。
3. 难点3-如果直接对最后结果取余数会报错，这里没有办法骗分的。先给一个结论，任何数的余数等于这个数的两个因子的余数乘积的余数，假设num%m = rem，且num=f1*f2, f1%m=rem1, f2%m=rem2. Then num=(n1*m+rem1)*(n2*m+rem2). Unfold it we get: num=n1*n2*m*m+n1*m*rem1+n2*m*rem1+rem1*rem2。很容易看到，这个展开式的余数就是rem1*rem2%m。所以在快速幂的时候，每一级乘幂结果我们都只返回这一级的余数。

注意，number=2,3,4直接返回手算解，避免特殊情况的复杂处理

本人小白，写的比较详尽，但应该比官解更突出要点，希望能帮到其他初学者。