2021.10.10 - JZ14.II.剪绳子 II

• 1. 题目
• 2. 思路
• • (1) 数学法
• 3. 代码

• 与之前的推论相同，唯一区别在于处理整数溢出的情况，需要手动计算3的n次方，在计算过程中不断对结果取余，防止溢出。
• 注意！由于是对1000000007取余，当原数乘以3时已经有可能超出int的取值范围，因此应该用long类型存储结果。

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        int mer = n / 3;
        int rem = n % 3;
        long res = 1;
        switch (rem) {
            case 2:
                while (mer > 0) {
                    res = (res * 3) % 1000000007;
                    mer--;
                }
                res = (res * 2) % 1000000007;
                break;
            case 1:
                while (mer > 1) {
                    res = (res * 3) % 1000000007;
                    mer--;
                }
                res = (res * 4) % 1000000007;
                break;
            default:
                while (mer > 0) {
                    res = (res * 3) % 1000000007;
                    mer--;
                }
                break;
        }
        return (int) res;
    }
}