网站建设如何自学/百度小说排行榜2020前十名

2020年12月4日 周五天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

这道题主体和 剑指offer 14. 剪绳子 一样，唯一不同的就是本题涉及到大数越界情况下的取余问题。

class Solution {
public:int cuttingRope(int n) {if (n <= 3) return n - 1;int a = n / 3, b = n % 3, ans = 0, mod = 1000000007;if (b == 0) ans = Pow(3, a, mod);else if (b == 1) ans = Pow(3, a - 1, mod) * 4 % mod; // *4后的结果可能大于mod，因此需要再次取余else ans = Pow(3, a, mod) * 2 % mod;return ans;}// 快速幂算法，对 1000000007 取余long long Pow(long long base, long long power, int mod){long long res = 1;while(power != 0){if(power&1)res = res * base % mod;power >>= 1;base = base * base % mod;}return res;}
};

这里使用的是快速幂算法，具体参考了这篇文章 快速幂算法（全网最详细地带你从零开始一步一步优化）。

参考文献

快速幂算法（全网最详细地带你从零开始一步一步优化）
《剑指offer 第二版》