题解 | #剪绳子（进阶版）#

题目：https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number long长整型 
# @return long长整型
#
class Solution:
    def fastpow(self, x, n):#写一个快速幂的函数
        res = 1
        while n>0:
            if n & 1:#n是奇数，此处等价于if(n%2==1)
                res = res*x%998244353  #可以再往上乘一个
            x =x*x%998244353#叠乘            
            n = n >> 1#减少乘次数，此处等价于n/2。
            #准确地说，如果n是偶数，n >> 1等于n/2；如果n是奇数，n >> 1等于n/2-1。
        return res
    
    def cutRope(self , number: int) -> int:
        if number==2:
            return 1
        elif number==3:
            return 2
#如果n是3的倍数，绳子全部剪为3，如9=3*3*3
#如果n对3求余等于1，我们剪出一个长度为4的，其他长度都是3，如10=3*3*4
#如果n对3求余等于2，我们剪出一个长度为2的，其他长度都是3，如11=3*3*3*2
        elif number%3==0:
            return self.fastpow(3,number//3)%998244353#等价于3**(number//3)
        elif number%3==1:
            return (self.fastpow(3,number//3-1)*4)%998244353#等价于3**(number//3-1)*4
        elif number%3==2:
            return (self.fastpow(3,number//3)*2)%998244353#等价于3**(number//3)*2

快速幂算法的思路：（搬运b站芸学习） alt