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

学到了，二分求乘和幂

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
  long long mod = 998244353;
  
    long long cutRope(long long number) {
      if (number <= 3) {
        return number - 1;
      } else if (number % 3 == 0) {
        // 刚好整除
        return pow(3, number / 3);
      } else if (number % 3 == 1) {
        //  剩下一则取出一个3凑成4
        return fast(pow(3, number / 3 - 1), 4);
      } else {
        //  剩下2直接相乘
        return fast(pow(3, number / 3), 2);
      }
    }
  
  long long fast(long long a, long long b) {
    long long res = 0;
    
    a %= mod;
    b %= mod;
    
    while (b) {
      if (b & 1) {
        //  累积的奇数和加上偶数和，最后为1一定会两者相加
        res += a;
        if (res >= mod) {
          res -= mod;
        }
      }
      
      b >>= 1;
      //  a+a = a*2 = a<<1
      a <<= 1;
      
      if (a >= mod) {
        a -= mod;
      }
    }
    
    return res;
  }
  
  long long pow(long long a, long long b) {
    long long res = 1;
    
    while (b) {
      if (b & 1) {
        res = fast(res, a);
      }
      
      a = fast(a, a);
      b >>= 1;
    }
    
    return res;
  }
};