题目

题解

这题写的我不行了，其实这题思路很简单，就是c++取余太麻烦了，我想写一个自己的pow()函数，用clion跑的结果和oj还不一样，取个余还有负数。也不知道咋回事，有知道的大神麻烦告知一下。
取余有两种，循环取余和快速幂取余，其时间复杂度也不同，详见这里。
而这道题由于要取余就不能用动态规划了，只能用推导出来的找3的方法。 题解来源于LUI和Magic_Conch，反正今天不想看了，回过头再看
这题的思路和算幂都好理解，就是取余和类型转换绕的我头晕
两种取余的方法。快速幂具体可以看50题

1. 循环取余

  • 时间复杂度$O(N)$
  • 空间复杂度$O(1)$
class Solution {
public:
    int cuttingRope(int n) {
        if(n==2)    return 1;
        if(n==3)    return 2;
        if(n==4)    return 4;
        long res=1;
        while(n>4){
            res*=3;
            res%=1000000007;
            n-=3;
        }
        return (int)(res*n%1000000007);//这里必须取括号，否则会优先计算res*n的值，报错会超出范围
    }
};

2. 快速幂

  • 时间复杂度$O(log{N})$
  • 空间复杂度$O(1)$
class Solution {
public:
    long long mypow(int x){//pow(n,x)
        if(x==0)
            return 1; 
        if(x%2)
            return 3*(mypow(x-1))%1000000007;
        else
        {
            long long half = mypow(x/2);
            return (half%1000000007*half%1000000007)%1000000007;    
        }
    }
    int cuttingRope(int n) {
        if(n<4)
            return n-1;
        int a = n%3,b = n/3;
        if(a==1)
            return mypow(b-1)*(long long)4%1000000007;
        if(a==2)
            return mypow(b)*(long long)2%1000000007;
        return mypow(b);
    }
};