剑指 Offer 14- II. 剪绳子 II

这题由于n的范围加大

数学方法 TAIFUZALE

循环求余 这是使得中间值取余不影响结果取余的理论保证 x^a % p = (x^(a-1) % p)(x % p) = ((x^(a-1) % p) x) % p

1
2
3

int ret = 1;
for(int i = 0; i < a; ++i)
    ret = ret * x % p

完整代码

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        int p = 1000000007;
        int a = n / 3;
        int b = n % 3;
        long ret = 1;
        for(int i = 0; i < (b == 1 ? a - 1 : a); ++i)
            ret = ret * 3 % p;
        if(b == 1)
            return ret * 4 % p;
        if(b == 2)
            return ret * 2 % p;
        return ret;

    }
};