题目描述

给你一根长度为 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。

https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/

题解

此题与 14-I.剪绳子I 相同，但是有大数越界情况下的取余问题。

数学 + 快速幂

直接用数学方法求结果，但是自己实现 pow(x, y) 函数，在其中加入大数取余操作。

class Solution {
    const int mod = 1000000007;

    // 快速幂并取余 O(logy)
    long pow_mod(long x, int y) {
        long res = 1;
        while (y) {
            if (y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }

    // // 循环求幂并取余 O(y)
    // long pow_mod(long x, int y) {
    //     long res = 1;
    //     for (int i = 0; i < y; ++i) res = res * x % mod;
    //     return res;
    // }

public:
    int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int quotient = n / 3, remainder = n % 3;
        switch (remainder) {
            case 0: return pow_mod(3, quotient);
            case 1: return pow_mod(3, quotient - 1) * 4 % mod;
            case 2: return pow_mod(3, quotient) * 2 % mod;
        }
        return -1;
    }
};