剑指offer 14-II. 剪绳子 II（大数求余问题）

剑指 Offer 14- II. 剪绳子 II - 力扣（LeetCode） (leetcode-cn.com)

本题只是在 "剪绳子 I" 的基础上增大了数据，因此我们只需要另外处理大数求余问题即可。

剪绳子I的题解：

剑指offer 14 - I. 剪绳子（贪心，DP）_Corux的博客-CSDN博客

目录

分析

代码

运行结果

---

分析

处理一般性的大数求余问题的方法。

pow(a,x) % N

N是一个不超过32位的int型数据，a小于N， 当x较大时，pow(a,x)很可能超过64位，无法整型来表示。

我们希望在求解pow(a, x)的过程中，一旦发现结果超过了N，便令结果mod N。

a的多少次幂刚好超过N呢？

设
pow(a, k-1) <= N < pow(a, k)
则
k = log(N) / log(a) + 1

 那么也就是说对于pow(a, y)，当y < k时，pow(a, y) <= N，此时不需要模运算；当y达到k时，pow(a, y)刚刚超过N，此时进行模运算即可。

因为x可写成以下形式：
x = p * k + q    ( 0 <= q <= k-1 )

所以：pow(a, x) = pow(pow(a, k), p) * pow(a, q)

因此 

pow(a, x) % N = pow( pow(a, k)%N, p ) * pow(a, q) % N

注意到pow(a, k)%N 和 pow(a, x)%N具有同样的形式，因此对其进行递归求解即可。

代码

class Solution {
    int N = 1000000007;
public:
    int cuttingRope(int n) {
        if (n == 2) return 1;       //处理两个特殊情况
        else if (n == 3) return 2;

        int x = n / 3, r = n % 3;
        if (!r) return R(3, x, N);
        else if (r & 1) return R(3, x - 1, N) * 4 % N;
        else return R(3, x, N) * 2 % N;
    }

    int64_t R(int a, int x, int N) {    //求pow(a, x) % N的函数
        if (!x) return 1;
        int k = log(N) / log(a) + 1;
        int p = x / k, q = x % k;
        return R(power(a, k) % N, p, N) * power(a, q) % N;
    }

    int64_t power(int a, int x) {   //自己写的pow函数，因为标准库pow函数返回的是double类型，转化成整型会丢失精度，在数值较大时表现的尤为明显
        if (!x) return 1;
        int64_t res = 1;
        while (x--) res *= a;
        return res;
    }
};

运行结果