题解 | #剪绳子（进阶版）#

C语言求剪绳子（进阶版）

解题思路

对于一段绳子16米 切割方式为 3 3 3 3 2 2，要想乘积足够大，需要优先切割段数3米，其次是2米，不能含有1，这道题就简化成了一个求快速幂的题型。先计算绳子能分多少个3米 多少个2米 然后求快速幂。

递归求快速幂

求 3^7为例，递归为 3*3^6 而3^6可以递归为 3^3 * 3^3，进行递归

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param number long长整型 
 * @return long长整型
 * C语言声明定义全局变量请加上static，防止重复定义
 */
long long mypow(int base,long long m){
    if(m==0)
        return 1;
    if(m%2==1){
        return base*mypow(base,m-1)%998244353;
    }
    else{
        long long temp=mypow(base,m/2);
        return temp*temp%998244353;
    }
    
}
long long cutRope(long long number ) {
    // write code here
    if(number==2)
        return 1;
    if(number==3)
        return 2;
    //其余的按照2 3 3 3 3的方式切割 不能有1
    long long count2=0;
    //含有3 的个数
    long long count3=number/3;
    //除3 余1 需要拿出来一个3 凑两个2
    if(number%3==1){
        count3--;
        count2=2;
        return (mypow(3,count3)*4%998244353);
    }
    //除3 余2 
    else if(number%3==2){
        count2=1;
        return (mypow(3,count3)*2%998244353);
    }
    return mypow(3,count3);
}