剪绳子（进阶版）

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param number long长整型
# @return long长整型
#
class Solution:
    """
    题目：
        NC287 剪绳子（进阶版）
        https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741?tpId=196&tqId=39738&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total&difficulty=&judgeStatus=&tags=/question-ranking
    借鉴：
        大神：妙蛙种子呱呱呱、牛客736356489号
    算法：
        贪心算法
        当number <= 3，直接返回number - 1
        当number == 4时，返回4
        当number >= 5时，能取3先取3，当小于5时，直接取该数
        这里需要注意的是：
            当number很大时，如果使用如下循环，容易超时。这里考察的另一个知识点就是快速幂运算。
            # while number > 4: # 这里需要使用快速幂运算，不然超时
            #     res = (res * 3) % MOD
            #     number -= 3
            # return res * number % MOD
    复杂度：
        时间复杂度：O(logN)
        空间复杂度：O(1)
    """

    def cutRope(self, number):
        # write code here
        def fastPow_rec(x, n): # 递归法
            if n == 0:
                return 1
            elif n == 1:
                return x
            else:
                part = fastPow_rec(x, n / 2) % MOD
                if n % 2 == 0:
                    ans = part * part % MOD
                else:
                    ans = part * part * x % MOD
                return ans

        def fastPow_ite(x, n): # 迭代法
            if n == 0:
                return 1
            elif n == 1:
                return x
            else:
                ans = 1
                while n > 0:
                    if n % 2 == 1:
                        ans *= x % MOD
                    x = x ** 2 % MOD
                    n /= 2
                return ans

        if number <= 3:
            return number - 1
        elif number == 4:
            return 4
        else:
            res, MOD = 1, 998244353
            cnt = number / 3
            if number % 3 == 0:
                res = fastPow_ite(3, cnt) % MOD
            elif number % 3 == 1:
                res = fastPow_ite(3, cnt - 1) * 4 % MOD
            else:  # number % 3 == 2
                res = fastPow_ite(3, cnt) * 2 % MOD
            return res


if __name__ == '__main__':
    s = Solution()

    # n = 4

    # n = 5

    # n = 874520

    n = 999999999

    res = s.cutRope(n)

    print res