题解 | #剪绳子（进阶版）#

剪绳子(进阶版)：最直观的想法是，快速幂加上快速乘法。剪绳子当每一段长度为3时乘积最大，故使用number对3取余得到res，取商得到num，当res等于0直接返回3的num次方，当res等于1则取一个3凑成4即返回3的num-1次方再乘以4，当res等于2直接返回3的num次方再乘以2。但是由于数据较大，故乘方运算要使用快速幂实现，而乘法运算要使用快速乘法即乘法转换为加法计算。具体注释如下面代码所示。

//乘法
long long mod=998244353;
// 将乘法转换为加法 计算a乘以b
long long fast(long long a,long long b)
{
    long long res=0;
    a%=mod;
    b%=mod;
    while(b)
    {
       // b的当前位为1
       if(b&1)
       {
           res+=a;
           res%=mod;
       }
       b>>=1;
       a<<=1;  // 相当于乘以2 因为b是二进制 b右移对应的a左移
       a%=mod;
    }
    return res;
}
// 快速幂运算计算a的b次方
long long quick(long long a,long long b)
{
    // 记录结果
    long long res=1;
    while(b)
    {
       //b的当前位为1 将其当前乘入结果
       if(b&1)
         res=fast(res,a);
       // 底数a向前一位代表进位 即为下一次的底数
       a=fast(a,a);
       // 指数b右移一位
       b>>=1;
    }
    return res;
}
long long cutRope(long long number) 
{
    // 长度为n分为m段 且m>1 n=2则1*1=1 n=3则1*2=2
    if(number<=3)
       return number-1;
    long long num=number/3;
    long long res=number%3;
    if(res==0)
       return quick(3,num);
    else if(res==2)
       return fast(2,quick(3,num));
    return fast(4,quick(3,num-1));
}