首页 > 试题广场 >

剪绳子（进阶版）

[编程题]剪绳子（进阶版）

热度指数：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 取模。

数据范围： $2\leq n \leq 10^{14}$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

示例1

输入

输出

说明

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

示例2

输入

输出

说明

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

示例3

输入

输出

908070737

算法知识视频讲解

Java

快乐仕忆

送给大家最后一个测试用例：

Assert.assertEquals(397254463L, cutRope(1000000000000000L));

发表于 2023-12-16 11:29:59 回复(0)

Java

^ǒ^月亮船^

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    final int MOD = 998244353;
    public long cutRope (long number) {
        // write code here
        if(number == 2){
            return 1;
        }
        if(number == 3){
            return 2;
        }
        
        if(number % 3 == 0){
            return pow(3, number/3);
        }else if(number % 3 == 1){
            return 2*2*pow(3, (number-4)/3)%MOD;
        }else{
            return (2*pow(3, (number-2)/3))%MOD;
        }
    }
    
    //快速幂函数:求a的n次幂
    public long pow(long a, long n){
        
        long result = 1;
        
        while(n > 0){
            if((n & 1) == 1){
                result = (result*a)%MOD;
            }
            a = (a*a)%MOD;
            n>>=1;
        }
        return result;
    }
}

发表于 2022-08-16 18:22:14 回复(0)

Java

YxY201903051225168

import java.util.*;
import java.math.BigDecimal;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number long长整型
     * @return long长整型
     */
    public long cutRope (long number) {
        // write code here
        if (number == 1) return 0;
        if (number == 2) return 1;
        if (number == 3) return 2;
        long num_3 = number / 3;
        long num_2 = (number - num_3 * 3) / 2;
        long num_1 = (number - num_3 * 3 - num_2 * 2);
        if (num_1 == 1) {
            num_3--;
            num_2 = num_2 + 2;
            num_1 = 0;
        }
        long res = 1;
        //(a * b) % mod = (a % mod * b % mod) % mod
        res = res * (powCal(3, num_3));
        //if (res > 998244353) res = res % 998244353;
        res = res * (powCal(2, num_2)) % 998244353;
        return res;
    }
    public long powCal(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a  % 998244353;
            }
            a = a * a % 998244353;
            b >>= 1;
        }
        return res;
    }
}

发表于 2022-05-15 15:00:26 回复(0)

Java

小明w

请问大佬为什么最后一例通不过啊，先取出a每一位的值是0或1，然后计算出每一位的成绩的模，最后在挨个相乘，只有最后一例，
100000000000000L过不了，求解

    public long cutRope (long number) {
        if (number <= 3) return number - 1;
        long a = number / 3;
        long b = number % 3;
        long c = 998244353L;

        int[] bits = new int[64];
        int i = 0;
        while(a > 0)
        {
            bits[i] = (int)(a % 2);
            a /= 2;
            i ++;
        }
        long[] pow = new long[i];
        pow[0] = 3;

        for(int j = 1; j < i; j ++)
        {
            pow[j] = pow[j-1] * pow[j-1];
            pow[j] %= c;
        }

        long rus = 1;

        for(int j = 0; j < i; j ++)
        {
            if(bits[j] == 1)
            {
                rus *= pow[j];
                rus %= c;
            }
        }
        if(b == 1)
        {
            rus = (rus / 3) * 4;
        }
        else if(b == 2)
        {
            rus *= 2;
        }
        rus %= c;
        return rus ;
    }

发表于 2022-03-12 09:22:29 回复(0)

Java

李橙子

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param number long长整型
* @return long长整型
*/
public long cutRope (long number) {
// 快速幂（利用上一题的公式法）

// 特殊值
if(number<4)
return number-1;
// 计算指数
long expo = number/3;

// 整除
if(number%3==0)
return fast(expo) % 998244353;
// 余1,凑成4
else if(number%3==1)
return (fast(expo-1)*4) % 998244353;
// 余2，直接返回
else
return (fast(expo)*2) % 998244353;
}

public long fast(long expo){
long product = 3;
long res=1;
while(expo!=0){
// 如果当前权重有
if((expo & 1) == 1){
res = (res * product) % 998244353;
}
// 累乘
product = (product * product) % 998244353;
// 指数右移1位，准备下次处理
expo = expo >>> 1;
}
return res;
}
}

发表于 2022-02-10 16:15:33 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

public class Solution {
    public long cutRope (long number) {
        // 快速幂（利用上一题的公式法）
        
        // 特殊值
        if(number<4)
            return number-1;
        // 计算指数
        long expo = number/3;
        
        // 整除
        if(number%3==0)
            return fast(expo) % 998244353;
        // 余1,凑成4
        else if(number%3==1)
            return (fast(expo-1)*4) % 998244353;
        // 余2，直接返回
        else
            return (fast(expo)*2) % 998244353;
    }
    
    public long fast(long expo){
        long product = 3;
        long res=1;
        while(expo!=0){
            // 如果当前权重有
            if((expo & 1) == 1){
                res = (res * product) % 998244353;
            }
            // 累乘
            product = (product * product) % 998244353;
            // 指数右移1位，准备下次处理
            expo = expo >>> 1;
        }
        return res;
    }
}

发表于 2022-02-04 18:26:39 回复(0)

Java

我不打朋友圈

//这个快速求幂函数很巧妙，算是这个题的一个难点所在，
//想清楚了就容易多了
import java.util.*;


public class Solution {
     final int MOD = 998244353;
    long pow(long a, long n){
       
        long ans = 1;
 
        while(n>0){
           if(n%2 == 1)ans = (ans*a)%MOD;
           a = (a*a)%MOD;
           n/=2;
       }
       return ans % MOD;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    public long cutRope (long number) {
        // write code here
        long result = 0;
        if(number <= 3) return number - 1;
        if(number % 3 != 1){
            if(number % 3 == 0)
                result = pow(3,number/3);
            if(number % 3 == 2)
                result =pow(3,number/3) * 2 % MOD;
        }else{
            result = pow(3,number/3 - 1) * 4 % MOD;
        }
        return result;
    }
}

发表于 2022-01-01 17:25:07 回复(0)

提交观点

问题信息

基础数学快速幂

难度：

9条回答 376收藏 3374浏览

通过挑战的用户

查看代码

国洪酱

2022-09-16 14:20:03
浙大码农哥

2022-09-16 10:55:25
追赶太阳的红太...

2022-09-15 09:57:50
牛客67494...

2022-09-15 08:19:01
聂莫黎

2022-09-14 16:12:53

剪绳子（进阶版）

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题