思路

这道题和剪绳子题是一模一样的，区别只在于该题数据范围很大。如果使用和剪绳子一样的做法，那么运行会超时。

剪绳子代码

class Solution {
public:
    int cutRope(int number) {
        if(number==2||number==3) return number-1;
        int res = 1;
        while(number>4)
        {
        	number-=3;
        	res*=3;
        }
        return number*res;
    }
};

如果这道题仍然用这种解法，程序必定会运行超时。其实这道题答案就是求3的高次幂。而求一个数的高次幂，我们可以使用快速幂算法来帮助我们优化时间复杂度。

剪绳子进阶代码

class Solution {
public:
    //快速幂运算（求base的power次幂）
    long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 998244353;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 998244353;
    }
    return result;
}
    long long cutRope(long long number) {
        if (number == 2) return 1;
        if (number == 3) return 2;
        if (number == 4) return 4;
        long cnt = number / 3; 
        long tail = number%3;
        if(tail==0) return fastPower(3,cnt)%998244353;
        else if(tail==1) return (fastPower(3,cnt-1) * 4)%998244353; //最后余4的情况
        else return (fastPower(3,cnt) * tail)%998244353;

    }
};