算法：贪心+快速幂

经典数学问题，可以用贪心思想分析，大于3的绳子剪出来的子绳子长度可以只包含2，3，且3优于2：
4 = 2+2 = 3+1，2·2 = 4，3·1=1；
5 = 2+3，23 = 6 > 5；
6 = 3+3 = 2+4, 3·3 = 9，2·4 = 8;
…
所以可以排除掉2,3以外的因数，然后确定2的个数小于等于2。分别讨论2的个数为0,1,2
0：全部为3，对应模3余0
1：有且仅有一个2，对应模3余2
2：2+2，22 = 4，对应模3余1

把多出来的2处理掉，再用快速幂求$3^N$的值即可:
把N看作一个二进制数，则$3^N$就是一系列幂为2次幂的数相乘
初始化累乘器为3。N的末尾如果是1，则结果乘以累乘器，累乘器平方，N右移一位，直到N为0.

时间复杂度

$O(logN)$

代码

class Solution {
public:
    int cuttingRope(int n) {
        typedef long long LL;
        if(n <= 3) return n - 1;
        LL res = 1;
        int mod = 1e9 + 7;
        if(n % 3 == 1) n -= 4, res = 4;
        if(n % 3 == 2) n -= 2, res = 2;
        // 3 ^ (k)
        int x = 3;
        for(int k = n/3; k > 0; k >>= 1){
            if(k & 1) res = res * x % mod;
            x = x * (LL)x % mod;
        }
        return res;
    }
};