题目的主要信息：

• 把一根长度为$nn$的绳子分成$mm$段，每段长度都是整数
• 求每段长度乘积的最大值
• 由于答案过大，请对 998244353 取模
• 进阶要求：空间复杂度：$O(1)O(1)$， 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$

数学推算

根据均值不等式，有：$\frac{n_1+n_2+\mathrm{.}\mathrm{.}\mathrm{.}+n_m}{m}\ge \sqrt[m]{n_1{n}_2\mathrm{.}\mathrm{.}\mathrm{.}{n}_m}\backslash frac\{n\_1+n\_2+...+n\_m\}\{m\}\backslash geq\; \backslash sqrt[m]\{n\_1n\_2...n\_m\}$，等号当且仅当$n_1=n_2=n_3=\mathrm{.}\mathrm{.}\mathrm{.}{n}_{m}n\_1=n\_2=n\_3=...n\_m$时成立，因为加法部分和是固定的绳子总长度，因此要使乘积最大，应该以相等的长度等分成多段。

如果将绳子按照每段长度为$xx$等分成$mm$段，则$n=mxn=mx$，乘积为$x^{m}x^m$，因为有$x^m=x^{\frac{n}{x}}=(x^{\frac{1}{x}}{)}^{n}x^m=x^\{\backslash frac\{n\}\{x\}\}=(x^\{\backslash frac\{1\}\{x\}\})^n$，因此当$x^{\frac{1}{x}}x^\{\backslash frac\{1\}\{x\}\}$取最大值时取最大值。

令$y=x^{\frac{1}{x}}y=x^\{\backslash frac\{1\}\{x\}\}$，即求这个函数的极值即可直到绳子等分成长度为多少可以使乘积最大。根据取对数、求导、求极值等一系列数学操作，得驻点为$x_0=ex\_0=e$，即极大值需要将绳子分成每段e，但是绳子长度只能是整数，靠近e的只有2 和3，二者分别代入公式，发现当$x=3x=3$是，乘积达到最大。

因此后续，使用贪心思想，不断将绳子分成每段长度为3即可，不足3的可以考虑，如果最后剩余的是2，直接乘上，如果最后剩余的是1，则取出一个3组成4分成长度为2的两段，因为$2\ast 2>1\ast 32*2>1*3$。

方法一：暴力乘法（超时）

具体做法：

不超过3的直接计算，超过3的不断累乘3，然后number减去3，直到最后不超过4。

class Solution {
public:
    long long cutRope(long long number) {
        if(number <= 3) //不超过3直接计算
            return number - 1;
        long long res = 1;
        while(number > 4){
            res *= 3; //连续乘3
            res = res % 998244353;
            number -= 3; 
        }
        return res * number % 998244353;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为绳子的长度，最坏需要计算$n\mathrm{/}3n/3$次
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：快速幂+快速乘法

具体做法：

方法一是计算累成，其实我们可以直接分成3种情况，计算幂。

情况一：n整除3，即可以全部完成分成长度为3的小段，一共$n\mathrm{/}3n/3$段，计算$3^{n\mathrm{/}3}3^\{n/3\}$即可；

情况二：n除3余1，需要拿出一个3个1组合称，一共$n\mathrm{/}3-1n/3-1$段长度为3的，2段长度为2的，计算$2\ast 2\ast 3^{n\mathrm{/}3-1}2*2*3^\{n/3-1\}$即可；

情况三：n除3余2，直接将剩下长度为2的段乘在之前的乘积上，计算$2\ast 3^{n\mathrm{/}3}2*3^\{n/3\}$即可。

计算幂为了缩短时间，采用快速幂加快速乘法优化：

快速幂。如果我们要计算$5^{10}5^\{10\}$，常规的算法是$5\ast 5=255*5=25$，然后再$25\ast 5=12525*5=125$，如此往下，一共是$99$次运算，即$n-1n-1$次。但是我们可以考虑这样：$5\ast 5=255*5=25$(二次）、$25\ast 25=62525*25=625$（四次）、$625\ast 625=\mathrm{.}\mathrm{.}\mathrm{.}625*625=...$（八次），这是一个二分的思维，运算次数缩减到了$lo{g}_{2}nlog\_2n$次，公式如下：

快速乘法。直接计算$x^{a}x^a$会超出long long的表示范围，因此我们可以考虑用加法来代替乘法，并在这其中取模。就比如$a\ast b=a\ast (b_1+b_2+b_3+\mathrm{.}\mathrm{.}\mathrm{.})a*b=a*(b\_1+b\_2+b\_3+...)$，其中$b_{i}b\_i$是数字$bb$的二进制各位，假设$a=5a=5$，$b=110101b=110101$，我们有$a\ast b=a\ast (100000\ast 1+10000\ast 1+1000\ast 0+100\ast 1+10\ast 0+1\ast 1)a*b=a*(100000*1+10000*1+1000*0+100*1+10*0+1*1)$，如下表所示可以换成加法运算并在加法中取模：

class Solution {
public:
    long long mod = 998244353;
    long long fast(long long x, long long y){ //快速乘法
        long long res = 0;
        x %= mod;
        y %= mod;
        while(y){
            if(y & 1){
                res += x; //加法代替乘法，防止爆long long
                if(res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if(x >= mod)
                x -= mod;
        }
        return res;
    }
    long long Pow(long long x, long long y){ //快速幂
        long long res = 1;
        while(y){
            if(y & 1) //可以再往上乘一个
                res = fast(res, x);
            x = fast(x, x); //叠加
            y = y >> 1; //减少乘次数
        }
        return res;
    }
    long long cutRope(long long number) {
        if(number <= 3) //不超过3直接计算
            return number - 1;
        if(number % 3 == 0) //能整除3
            return Pow(3, number / 3);
        else if(number % 3 == 1) //最后剩余1
            return fast(Pow(3, number / 3 - 1), 4); //4*3^{n-1}
        else //最后剩余2
            return fast(Pow(3, number / 3), 2); //2*3^n
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，快速幂相当于二分法，因此复杂度为$O(lo{g}_{2}n)O(log\_2n)$
• 空间复杂度：$O(1)O(1)$，无额外空间