现需要将一根长为正整数 bamboo_len 的竹子砍为若干段（至少两段），每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。

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

示例 1：

**输入：**bamboo_len = 12
**输出：**81

提示：

2 <= bamboo_len <= 1000

通过数学推导（算术几何平均值不等式），将一个正数拆分成若干相等部分时，每部分越接近自然常数

1
e \approx 2.718

乘积最大。在正整数中，最接近 e 的是 3，其次是 2。

使用贪心算法，由于我们要尽可能多地用 3，剩下的部分会有三种情况：

余数为 0：刚好全部分成 3，乘积为

1
3^{k}

余数为 1：最后剩下 3 * 1 ，这不如把一个 3 匀出来，变成 2 * 2 。乘积为 3^{k-1} * 4。

余数为 2：最后剩下一个 2，直接乘上去。乘积为 3^{k} * 2。

快速幂：

1
2
3
4
5
6
7
8
9
10
11
12
long long qremainder(long long x, long long a, long long MOD) {
    long long rem = 1;
    // 其实就是求a的二进制表示
    while (a > 0) {
        if (a % 2 == 1) {
            rem = (rem * x) % MOD;
        }
        x = (x * x) % MOD;
        a /= 2;
    }
    return rem;
}

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public : int cuttingBamboo(int bamboo_len) {
        if (bamboo_len == 2 || bamboo_len == 3)
            return bamboo_len - 1;

        long long MOD = 1000000007;
        long long a = bamboo_len / 3;
        long long b = bamboo_len % 3;
        long long rem;
        switch (b) {
        case 0:
            return qremainder(3, a, MOD);
        case 1:
            return (qremainder(3, a - 1, MOD) * (long long)4) % MOD;
        case 2:
            return (qremainder(3, a, MOD) * (long long)2) % MOD;
        }
        return -1;
    }
    long long qremainder(long long x, long long a, long long MOD) {
        long long rem = 1;
        while (a > 0) {
            if (a % 2 == 1) {
                rem = (rem * x) % MOD;
            }
            x = (x * x) % MOD;
            a /= 2;
        }
        return rem;
    }
};