首页 > 试题广场 >

剪绳子（进阶版）

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

热度指数：22906 时间限制：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

算法知识视频讲解

Python 3

牛客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)

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

我不打朋友圈

//这个快速求幂函数很巧妙，算是这个题的一个难点所在，
//想清楚了就容易多了
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)

C++

Spectre_

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    long long cutRope(long long number) {
        // 时间复杂度O(logN)，空间复杂度O(1)
        if (number <= 3) return number - 1;
        if (number % 3 == 0) return Pow(3, number / 3) % MOD;
        else if (number % 3 == 1) return Pow(3, number / 3 - 1) * 4 % MOD;
        else return Pow(3, number / 3) * 2 % MOD;
    }
    long long Pow(long long x, long long y) {
        long long ans = 1;
        while (y) {
            if (y % 2 == 1) ans = ans * x % MOD;
            x = x * x % MOD;
            y /= 2;
        }
        return ans;
    }
    long long MOD = 998244353;
};

发表于 2022-11-19 15:42:04 回复(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

快乐仕忆

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

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

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

秋叶红霜CCCCCC

class Solution:
    def cutRope(self, n: int) -> int:
        if n <= 3: return n - 1

        a = n // 3 - 1 # 快速幂的指数（已剥离余数3，4，5）
        b = n % 3 # 最后的余数：3，4，5对应乘3，乘2*2，乘3*2
        d, res = 3, 1 # 以3为底

        # 快速幂，不断翻倍基底d
        while a > 0:
            if a % 2: res = (res * d) % 998244353
            d = d ** 2 % 998244353
            a //= 2
            
        if b == 0: return (res * 3) % 998244353
        if b == 1: return (res * 4) % 998244353
        return (res * 6) % 998244353

发表于 2022-11-08 13:04:41 回复(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)

布加迪.威龙

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

发表于 2022-07-21 16:58:52 回复(0)

Python2

菜鸡升职记

# -*- 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

发表于 2022-07-06 14:10:12 回复(0)

C++

牛客321181780号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number long长整型
     * @return long长整型
     */
    const long long MOD = 998244353;

    long long cutRope(long long n) {
        //n > 1, 1 < m <= n
        switch (n) {
            case 2:
                return 1;
            case 3:
                return 2;
            case 4:
                return 4;
        }
        long long t3 = n / 3;
        switch (n % 3) {
            case 1:
                return qPow(3, t3 - 1) * 4 % MOD;
            case 2:
                return qPow(3, t3) * 2 % MOD;
            case 0:
                return qPow(3, t3);
            default:
                return 1;
        }
    }

    long long qPow(long long q, long long k) {
        if (k == 0)return 1;
        long long now = q, ans = 1;
        while (k) {
            if (k & 1) {
                ans = ans * now % MOD;
            }
            k >>= 1;
            now = now * now % MOD;
        }
        return ans;
    }
};快速幂

发表于 2022-07-01 09:22:04 回复(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)

Python 3

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)

記憶H

public class ShengZi {
    public static void main(String[] args) {
        System.out.println(cutRope(7));
    }

    public static long cutRope(long number) {
        // write code here
        long result = 0;
        if (number <= 3) {
            result = number - 1;
        } else {
            long x = number % 3;
            if (x == 0) {
                result = calculatePower(3, (long) (number / 3));
            }
            if (x == 1) {
                result = 4 * calculatePower(3, (long) (number / 3 - 1));
            }
            if (x == 2) {
                result = 2 * calculatePower(3, (long) (number / 3)) ;
            }
        }
        return result% 998244353;
    }

    public static long calculatePower(long num, long power) {
        long sum = 1;
        while (power > 0) {
            if (power % 2 > 0) {
                sum = (sum * num) % 998244353;
            }
            num = num * num % 998244353;
            power = power / 2;
        }
        return sum;
    }
}

编辑于 2021-11-03 14:17:16 回复(0)

C++

牛客498512030号

c++版本，构建3最多的情况。

然后写一个替代pow（）的函数，计算幂次方。

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param number long长整型
* @return long长整型
*/
long long cutRope(long long number)
{
long long mod=998244353;

long long n=number;
if (n == 2)
{
return 1;
}
if (n == 3)
{
return 2;
}

long long x = n % 3;
long long y = n / 3;

if (x == 0)
{
return (long long) qiuyu(3, y)%mod;
}
else if (x == 1)
{
return 2 * 2 * (long long) qiuyu(3, y - 1)%mod;
}
else
{
return 2 * (long long) qiuyu(3, y)%mod;
}
}


long long qiuyu(long long a, long long b )
{
long long mod=998244353;
long long res=1;
while (b>0)
{
if(b%2)
{
res = (res * a) % mod;
}
a=a*a%mod;
b=b/2;
}
return res;

}

};

发表于 2021-11-02 15:30:59 回复(0)

提交观点

问题信息

基础数学快速幂

难度：

18条回答 322收藏 1966浏览

通过挑战的用户

查看代码

国洪酱

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

剪绳子（进阶版）

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题