首页 > 试题广场 >

剪绳子（进阶版）

[编程题]剪绳子（进阶版）
  • 热度指数：26397 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

由于答案过大，请对 998244353 取模。

数据范围：
进阶：空间复杂度 O(1) ， 时间复杂度 O(logn)

示例1

输入

4

输出

4

说明

拆分成 2 个长度为 2 的绳子，2 * 2 = 4
示例2

输入

5

输出

6

说明

剪成一个长度为 2 的绳子和一个长度为 3 的绳子，答案为2*3=6
示例3

输入

874520

输出

908070737
算法知识视频讲解
添加回答
Python 3
Vivimore头像 Vivimore 
class Solution:
    mod = 998244353
    def q_mul(self, a, b, mod):  # 快速计算(a*b) % mod
        ans = 0
        while b:
            if b & 1:   # 判断当前位是否为1
                ans = (ans + a) % mod  # ans+=a
            b >>= 1  # b向前移位
            a = (a + a) % mod  # 更新a
        return ans
    def q_pow(self, a, b, mod):  # 快速计算(a^b) % mod
        ans = 1
        while b:
            if b & 1:
                ans = self.q_mul(ans, a, mod)  # ans*=a
            b >>= 1
            a = self.q_mul(a, a, mod)
        return ans
    def cutRope(self , n: int) -> int:
        if n <= 3:
            return n -1
        if n % 3 == 0:
            return self.q_pow(3, n // 3, self.mod)
        if n % 3 == 1:
            return self.q_mul(self.q_pow(3, n // 3 -1, self.mod), 4, self.mod)
        else:
            return self.q_mul(self.q_pow(3, n // 3, self.mod), 2, self.mod)
发表于 2022-05-13 10:46:38 回复(0)
Python 3
四片三明治头像 四片三明治 
class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        if number<=3:
            return number-1
       # res=1
        if number%3==1:
            n=number//3-1
            res=self.new_pow(3,n)*4
        elif number%3==0:
            n=number//3
            res=self.new_pow(3,n)
        else:
            n=number//3
            res=self.new_pow(3,n)*2
        return res%998244353
    def new_pow(self,a,n):
        #快速幂函数
        if n==0:
            return 1
        if n%2==1:
            return self.new_pow(a, n-1)*a%998244353
        else:
            temp=self.new_pow(a, n//2)%998244353
            return temp*temp%998244353

发表于 2022-04-01 16:27:08 回复(0)
Python 3
北风扬尘尘飞扬头像 北风扬尘尘飞扬 
class Solution:
    def cutRope(self, number: int) -> int:
        # 尽可能切割出3
        if number == 2:
            return 1
        if number == 3:
            return 2

        if number % 3 == 1:
            return self.pow(number// 3-1) * 4%998244353
        if number % 3 == 2:
            return self.pow(number// 3) * 2%998244353
        else:
            return self.pow(number // 3)%998244353

    def pow(self, n, base=3):  # 快速幂
        if n==0:
            return 1
        if n % 2 == 0:
            mul = self.pow(n //2) 
            return mul * mul%998244353 
        else:
            return base * self.pow(n - 1) %998244353
放一个Python3的递归快速幂。
发表于 2022-03-12 17:29:44 回复(0)
Python 3
牛客736356489号头像 牛客736356489号
防止指数太大影响求余，所以下一个log n的函数求指数的余数。 
class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        a, b = number // 3, number % 3
        p = 998244353
        if b==0: return self.qiuyu(3, a, p)
        elif b==1: return self.qiuyu(3, a-1, p) * 4 % p
        else: return self.qiuyu(3,a,p) * 2 % p
        
    def qiuyu(self,x,n,p):
        res=1
        while n>0:
            if n%2: res = (res * x) % p
            x = x ** 2 % p
            n //= 2
        return res


发表于 2021-10-30 16:14:18 回复(1)
提交观点

问题信息

基础数学 快速幂
难度：
4条回答 3373浏览

热门推荐

通过挑战的用户

查看代码

相关试题

剪绳子（进阶版）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号