剪绳子（进阶版）

C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2022-02-08

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;
}
};

C++ 解法, 执行用时: 2ms, 内存消耗: 392KB, 提交时间: 2022-02-10

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

C++ 解法, 执行用时: 2ms, 内存消耗: 440KB, 提交时间: 2021-12-13

class Solution {
public:
    long long mod = 998244353;
    long long fast(long long x, long long y){ //快速乘法
        long long res = 0;
        x %= mod;
        y %= mod;
        while(y){
            if(y & 1){
                res += x; //加法代替乘法，防止爆long long
                if(res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if(x >= mod)
                x -= mod;
        }
        return res;
    }
    long long Pow(long long x, long long y){ //快速幂
        long long res = 1;
        while(y){
            if(y & 1) //可以再往上乘一个
                res = fast(res, x);
            x = fast(x, x); //叠加
            y = y >> 1; //减少乘次数
        }
        return res;
    }
    long long cutRope(long long number) {
        if(number <= 3) //不超过3直接计算
            return number - 1;
        if(number % 3 == 0) //能整除3
            return Pow(3, number / 3);
        else if(number % 3 == 1) //最后剩余1
            return fast(Pow(3, number / 3 - 1), 4); //4*3^{n-1}
        else //最后剩余2
            return fast(Pow(3, number / 3), 2); //2*3^n
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 468KB, 提交时间: 2022-03-12

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    long long cutRope(long long number) {
        //至少剪成两段
        if( number == 2 )   return 1 ;
        if( number == 3 )   return 2 ; 
        if( number == 4 )   return 4 ;
        
        long long  res = 1  ;
        long long a = number/3  ;
        long long b = number%3 ;
        if(b == 1) 
        {
            a = a-1 ;
            res = 4 ;
        }else if(b==2){
            res = 2 ;
        }
        long long ans = res%998244353  ;
        //============ 循环求余 , 复杂度O(N)
        // for(int i = 1 ; i < a ; i++ )
        // {
        //     res = res * 3 % 1000000007 ;           
        // }
        //============ 快速幂求余 (二分)   , 复杂度 O(log2N)
        long long  x = 3 ;
        while(a>0)
        {
            if( a%2 == 1 )
            {
                res = res * x % 998244353  ;
            }
            x = x * x % 998244353 ;
            a /= 2; 
        }
        return res ;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 468KB, 提交时间: 2021-11-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    long long cutRope(long long number) {
        // write code here
        if(number<=3) return number-1;
        long long cnt=number/3;
        if (number % 3 == 0) {
            return pow1(cnt) % 998244353;
        } else if (number % 3 == 1) {
            cnt--;
            return 2 * 2 * pow1(cnt) % 998244353;
        } else {
            return 2 * pow1(cnt) % 998244353;
        }
    }
    
    long long pow1 (long cnt) {
        if (cnt == 0) return 1;
        if (cnt == 1) return 3;
        long long part = pow1(cnt / 2);
        if (cnt % 2 == 0) return part * part % 998244353;
        return 3 * part * part % 998244353;
    } 
};

详情