给你一根长度为 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 取模。
数据范围：
进阶：空间复杂度 )
， 时间复杂度 )
[编程题]剪绳子（进阶版）
精华题解
题目的主要信息：
把一根长度为nnn的绳子分成mmm段，每段长度都是整数
求每段长度乘积的最大值
由于答案过大，请对 998244353 取模
举一反三：
学习完本题的思路你可以解决如下题目：
JZ14. 剪绳子
方法：快速幂+快速乘法(推荐使用)
知识点1：贪心思想
贪心思想属于动态规划思想中
展开全文
题目的主要信息：
把一根长度为nnn的绳子分成mmm段，每段长度都是整数
求每段长度乘积的最大值
由于答案过大，请对 998244353 取模
进阶要求：空间复杂度：O(1)O(1)O(1)， 时间复杂度：O(log2n)O(log_2n)O(log2n)
数学推算
根据均值不等式，有：n1+
展开全文
3个数越多答案越大，所以n%3有三种情况:
余数为0直接做3^(n/3)
余数为1做4*3^((n-4)/3)
余数为2做2*3^((n-2)/3)
代码技巧部分：因为指数会很大如果用Math的函数效率低，这种情况可以用快速幂去做，比如a^n次方要n次的相乘，快速幂只需要logn次
import
展开全文
就是要重写pow函数 不然复杂度太大
有两点：一个是求次方的时候遇到偶数可以拆开来；另一个是可以提前做模运算
证明如图：
1.求模
首先是求模运算的性质。(a*b)%p = [(a%p) * (b%p)] % p
证明：
2.求次方
除了
展开全文
C语言求剪绳子（进阶版）
解题思路
对于一段绳子16米 切割方式为 3 3 3 3 2 2，要想乘积足够大，需要优先切割段数3米，其次是2米，不能含有1，这道题就简化成了一个求快速幂的题型。先计算绳子能分多少个3米 多少个2米 然后求快速幂。
递归求快速幂
求 3^7为例，递归为 3*3^6 而3^
展开全文
3作指数最好，不明白的看《剪绳子》中等题。
然后使用快速幂，时间复杂度O(logn)
注意大数越界问题。python可以不用考虑。
class Solution:
def cutRope(self, n:&
展开全文
题目主要信息
1、给出一根长度为n的绳子
2、将绳子截成m段，m>2，使得所有乘积最大
方法一:贪心算法
具体方法
本题是JZ14的进阶版，主要的区别在于绳子的长度在JZ14中为小于60，二在本题中为10的14次方，因此JZ14中的动态规划方法在本题中无法使用。
首先，我们可以把这题转化成一道
展开全文
思路
这道题和剪绳子题是一模一样的，区别只在于该题数据范围很大。如果使用和剪绳子一样的做法，那么运行会超时。
剪绳子代码
class Solution {
public:
int cutRope(int number) {
if(number==2||number==3) r
展开全文
剪绳子(进阶版)：最直观的想法是，快速幂加上快速乘法。剪绳子当每一段长度为3时乘积最大，故使用number对3取余得到res，取商得到num，当res等于0直接返回3的num次方，当res等于1则取一个3凑成4即返回3的num-1次方再乘以4，当res等于2直接返回3的num次方再乘以2。但是由于数
展开全文
长度为n的绳子(n为正整数)，截为m段(每段绳子的长度都为正整数)，求m段绳子的乘积最大值；
等价于
n=n1+n2+......+nn;求n1n2...nn 的最大值；
对于一个正整数a，若(a−d)×d>a(a-d) \times d>a(a−d)×d>a,d为正整数。
则a&
展开全文
class Solution {
public:
long long mod = 998244353;
//快速乘法
long long fast(long long x, long long y){
long long res = 0;
x
展开全文
问题信息
难度：
20条回答
376收藏
3371浏览
通过挑战的用户
查看代码-
2022-09-16 14:20:03 -
2022-09-16 10:55:25 -
2022-09-15 09:57:50 -
2022-09-15 08:19:01
-
2022-09-14 16:12:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
