剑指 Offer 14- II. 剪绳子 II——java

这一题最开始写的时候就懵懵的，看了解析以为懂了，今天再写又不会了，重新写一下思路。还是参考大佬的解析。

推论一： 将绳子以相等的长度等分为多段 ，得到的乘积最大。
推论二： 尽可能将绳子以长度 3 等分为多段时，乘积最大。

如果数字不大，根据推论和切分规则就能直接求结果，但是本题涉及大数越界情况下的求余问题，如2^1000 % 100000，它在运算途中就越界了，因此要再加上采取快速幂求余算法。
从快速幂取余算法思路详解可以得到此算法公式

困惑我的是为什么幂指数要从n/3-1开始，如果从n/3开始，如果余数为1，res/3*4%c的结果就不正确。

class Solution { 
    int c=1000000007;
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        int p=n%3;
        long res = 1;
        long a = 3; 
        int b=n/3-1;
        while(b > 0){
            if (b%2 ==1) res = (res*a)%c;
            a = (a*a)%c;
            b/=2;
        }
        if(p==0) return (int)(res*3%c);
        else if(p==1) return (int)(res*4%c);
        else return (int)(res*6%c);
    }
}