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

• f(2) = 1, f(3) = 2, f(4) = 4...
• 当n >= 4时， f(n) >= n 所以结果应该用2、3乘积表示
• 证明：f(n) = f(n - m) * m 当 m 大于 3 时， m <= f(m)
• 因此f(n) = 3 ^ x * 2 ^ y
• n % 3 = 0, x = n / 3，y = 0
• n % 3 = 1, x = n / 3 - 1, y = 2
• n % 3 = 2, x = n / 3, y = 1

public:
    long long M = 998244353;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    // return num ^ x
    long long myPow(long long num, long long x) {
        long long ans = 1;
        while (x) {
            if (x & 1)
                ans = ans * num % M;
            num = num * num % M;
            x >>= 1;
        }
        return ans;
    }
    long long cutRope(long long number) {
        // write code here
        if (number <= 3)
            return number - 1;
        
        long long num_3 = number / 3;
        int num_2;
        if (number % 3 == 0)
            num_2 = 1;
        else if (number % 3 == 1) {
            --num_3;
            num_2 = 4;
        } 
        else 
            num_2 = 2;
        
        long long ret = myPow(3, num_3) % M;
        return (ret * num_2) % M;
    }
};