描述

题目描述

首先给定了我们一个长度为$nn$的绳子, 然后我们需要把这个绳子分成$mm$段, 然后我们问我们这个$mm$段的最大的乘积是多少

题解

解法一: 我们暴力思考, 进行一个数学推导

实现思路

我们可以对这个考虑一下数学思想的一个证明

根据算数几何均值不等式可以知道以下结论

得到推论: 将绳子以相等的长度分为多段得到的乘积最大

我们将绳子按照$xx$长度等分成为$mm$段, $n==m\ast xn\; ==\; m\; *\; x$, 然后我们的乘积就是$x^{m}x\; ^\; m$, 然后我们可以得到这样的一个式子

我们其实就是对于最后的式子求极大值, 这个根据求导可得, 这里不过于赘述, 最后我们可以知道驻点是$x==ex\; ==\; e$

然后我们的切分长度要求是为整数, 我们考虑$22$和$33$哪一个更是接近我们的$ee$

我们可以把这个$22$和$33$分别带入我们上述的$x^{\frac{1}{x}}x\; ^\; \backslash frac\{1\}\{x\}$, 我们可以发现我们的$33$的值更大, 所以我们每次最好的方式就是每次都尽可能的切成长度为$33$的

那么我们的算法流程就是可以确定了下来

1. 如果我们按照长度为$33$进行一个切分, 如果最后剩下的是$00$, 不用考虑了
2. 如果最后留下来的是$22$, 我们不拆分
3. 如果最后留下来的是$11$, 我们把之前的一个$33$变成$2+22\; +\; 2$

代码实现

class Solution {
    const int mod = 998244353;
   public:
    long long cutRope(long long number) {
        if (number <= 3) return number - 1;
        // 如果不到3我们可以直接计算
        long long cnt = 0;
        while (number > 4) {
            cnt += 1;
            number -= 3;
        }
        // 计算我们的这个有多少段3
        long long res = 1;
        for (int i = 1; i <= cnt; i++) res = (res % mod * 3 % mod) % mod;
        // 得到我们最后的答案
        return res * number % mod;
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们需要运算$n\mathrm{/}3n\; /\; 3$次, 是$O(n)O(n)$级别的

空间复杂度: $O(1)O(1)$

理由如下: 我们只引入了常数级别的空间

解法二: 快速幂

实现思路:

首先我们要考虑这么一个问题, 这个数据范围如果我们正常的$O(n)O(n)$的做法肯定是会$TLETLE$, 那么我们就是需要考虑一种算法这种的时间复杂度要可以达到$\sqrt{n}\backslash sqrt\{n\}$或者是$lognlogn$, 那么我们再去考虑我们上面慢在哪里, 我们是不是慢在一次次的寻找上面, 那么我们其实可以发现我们最简单的一个问题, 如果优化这个方面, 我们可以得到以下的算法思路

1. 如果我们可以整除$33$, 那么我们可以直接计算$3^{\frac{n}{3}}3\; ^\; \backslash frac\{n\}\{3\}$
2. 如果我们除$33$余$11$, 那么我们结果就是$4\ast 3^{\frac{n}{3}-1}4\; *\; 3\; ^\; \{\backslash frac\{n\}\{3\}\; -\; 1\}$
3. 如果我们余$22$, 我们结果就是$2\ast 3^{\frac{n}{3}}2\; *\; 3\; ^\; \backslash frac\{n\}\{3\}$

代码实现

class Solution {
    const long long mod = 998244353;

   public:
    long long qpow(long long a, long long b) {
        long long res = 1 % mod;
        a %= mod;
        while (b) {
            if (b & 1) res = res * a % mod;
            // 如果我们这位的二进制有值, 那么我们可以把这位乘上他的权重
            a = a * a % mod;
            // 更新权重
            b >>= 1;
            // 调整我们的b
        }
        return res;
    }
    // 快速幂
    long long cutRope(long long number) {
        if (number <= 3) return number - 1;
        // 如果不到3我们可以直接计算
        if (number % 3 == 0) return qpow(3, number / 3) % mod;
        // 如果正好整除
        else if (number % 3 == 1) return qpow(3, number / 3 - 1) * 4 % mod;
        // 如果最后余1
        else return qpow(3, number / 3) * 2 % mod;
        // 如果余是2 
    }
};

时空复杂度分析

时间复杂度: $O(logn)O(logn)$

理由如下: 我们的快速幂本质就是我们对我们的二进制位和它们的权值进行一个计算, 那么我们也就是需要遍历我们的所有的二进制位, 然后我们一个数的二进制位数也就是$lognlogn$级别的

空间复杂度: $O(1)O(1)$

理由如下: 我们未引用额外的空间