14(2)-剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

这道题就很难使用剪绳子1中的动态规划了，我们还是使用数学方法，计算绳子包含几个3长度的段，但是在计算乘积时需要注意，由于乘积过大会溢出，所以需要在计算中间就进行取模运算，以下是求余运算规则，可以看到在乘法中对每一个因子进行求余最后在求余与将乘法结果进行求余结果是一致的。 $$ (xy)%p=[(x%p)(y%p)]%p $$

public int cuttingRope(int n) {
          if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
        long res = 1;
        while(n > 4){
            res *= 3;
            res  = res % 1000000007; //对中间结果进行求余
            n -= 3;
        }
        return (int) (res * n % 1000000007); //不要忘记最后的求余
    }