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

就是要重写pow函数 不然复杂度太大

有两点：一个是求次方的时候遇到偶数可以拆开来；另一个是可以提前做模运算

证明如图：

1.求模

首先是求模运算的性质。(a*b)%p = [(a%p) * (b%p)] % p

证明：

2.求次方

除了对求模运算的优化，还要优化次方。

所以说本来要循环10次计算3的10次方，变成了9的5次方，然后5=1+4，编程了9*9^4，=9*81^2。运算的复杂度小了很多！！

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number long长整型 
# @return long长整型
#
class Solution:
    # 重写的幂函数
    # 快速幂的两个数学原理在题解
    def pow2(self,x,y):
        # 如果说幂就是0，则返回0次方的结果1
        if(y==0):
            return 1
        # 如果说幂是1，则放回x本身
        if(y==1):
            return x
        
        
        # 考虑到3^10 = (3^5)*(3^5)，后面的幂递归调用pow2函数
        # 所以后半部分就是对10的整除2 计算除3^5
        
        # 然后计算3^5时，成了3 *(3^2)*(3^2)，后面的幂递归调用pow2函数
        part = self.pow2(x,y//2)
        # 如果说原先的幂是10，那么结果直接相乘，然后再取余数。
        
        # 如果说原先的幂是5， 那么结果要多乘一个之前少掉的一次3
        if(y%2==0):
            return part*part%998244353
        else:
            return x*part*part%998244353
    
    def cutRope(self , number: int) -> int:
        # write code here
        if number ==2:
            return 1
        if number==3:
            return 2
        retans=1
        # 凑3 越多越好，如果结果剩下是1 也就是说
        # 最后一次是4-3=1 则返回上一步 乘4，而不是乘3
        # 最后一次是3-3=3 则返回结果
        # 最后一次是5-3=2 则返回结果*2
        ans3=int(number/3)
        if number%3==1:
            retans=self.pow2(3,ans3-1)
            return (retans*4)%998244353
        elif number%3==0:
            retans=self.pow2(3,ans3)
            return retans
        else:
            retans=self.pow2(3,ans3)
            return retans*2%998244353