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

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param number long长整型 
        * @return long长整型
    */
    fun cutRope(number: Long): Long  {
        if(number == 2L) return 1
        else if(number == 3L) return 2
        var times = number / 3
        if(number % 3 == 0L) return getSum(times)
        //当余数为1的时候1*3小于2*2所以有getSum(times - 1) * 4
        else if(number % 3 == 1L) return getSum(times - 1) * 4 % 998244353
        else return getSum(times) * 2 % 998244353
    }
    
    private fun getSum(value: Long): Long {
        var v = 3L
        var result = 1L
        var t = value
        while(t > 0) {
            //快速幂乘 比如value=3，那么就是3*3*3，第一次遍历t and 1 == 1L为true所以计算result * v，得result=3
            //然后计算v = v * v，得v=9，然后t = t shr 1，得t=1，然后进行第二轮计算，先计算t and 1 == 1L为true，
            //然后计算result = result * v，得result= 27，然后计算t = t shr 1，得t=0，然后退出循环得到结果为27
            if(t and 1 == 1L) result = result * v % 998244353
            v = v * v % 998244353
            t = t shr 1
        }
        return result
    }
}