剑指 Offer 14- II. 剪绳子 II

剑指 Offer 14- II. 剪绳子 II

在 剑指 Offer 14- I. 剪绳子的基础上加上快速幂

class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3)return n-1;
        int b=n%3,a=n/3-1,mod=1e9+7;
        long long res=1,x=3;
        while(a){
            if(a&1)res=(res*x) % mod;
            a>>=1;
            x=(x*x) % mod;
        }
        if(b==0)return (res*3) % mod;
        else if(b==1)return (res*4) % mod;
        else return (res*6) % mod;
    }
};