leetbook_ioa/docs/LCR 132. 砍竹子 II.md
切分规则的推导流程请见上一题「砍竹子 I」。
{:align=center width=600}
大数越界： 当 $a$ 增大时，最后返回的 $3^a$ 大小以指数级别增长，可能超出 int32 甚至 int64 的取值范围，导致返回值错误。
大数求余问题： 在仅使用 int32 类型存储的前提下，正确计算 $x^a$ 对 $p$ 求余（即 $x^a \odot p$ ）的值。
解决方案： 循环求余 、 快速幂求余 ，其中后者的时间复杂度更低，两种方法均基于以下求余运算规则推出：
$$ (xy) \odot p = [(x \odot p)(y \odot p)] \odot p $$
根据求余运算性质推出（∵ 本题中 $x<p$，∴ $x \odot p = x$ ）：
$$ x^a \odot p = [(x ^{a-1} \odot p)(x \odot p)] \odot p=[(x ^{a-1} \odot p)x] \odot p $$
利用此公式，可通过循环操作依次求 $x^1, x^2, ..., x^{a-1}, x^a$ 对 $p$ 的余数，保证每轮中间值 rem 都在 int32 取值范围中。封装方法代码如下所示。
# 求 (x^a) % p —— 循环求余法
def remainder(x, a, p):
rem = 1
for _ in range(a):
rem = (rem * x) % p
return rem
时间复杂度 $O(N)$ ： 其中 $N=a$ ，即循环的线性复杂度。
根据求余运算性质可推出：
$$ x^a \odot p = (x^2)^{a/2} \odot p = (x^2 \odot p)^{a / 2} \odot p $$
当 $a$ 为奇数时 $a/2$ 不是整数，因此分为以下两种情况（ ''$//$'' 代表向下取整的除法）：
$$ {x^a \odot p = } \begin{cases} (x^2 \odot p)^{a // 2} \odot p & \text{, $a$ 为偶数} \ {[(x \odot p)(x ^{a-1} \odot p)] \odot p = [x(x^2 \odot p)^{a//2}] \odot p} & \text{, $a$ 为奇数} \ \end{cases} $$
解析： 利用以上公式，可通过循环操作每次把指数 $a$ 问题降低至指数 $a//2$ 问题，只需循环 $\log_2(N)$ 次，因此可将复杂度降低至对数级别。封装方法代码如下所示。
# 求 (x^a) % p —— 快速幂求余
def remainder(x, a, p):
rem = 1
while a > 0:
if a % 2: rem = (rem * x) % p
x = x ** 2 % p
a //= 2
return rem
帮助理解： 根据下表， 初始状态 $rem=1$, $x=3$, $a=19$, $p=1000000007$ ，最后会将 $rem \times (x^a \odot p)$ 化为 $rem \times (x^0 \odot p) = rem \times 1$ 的形式，即 $rem$ 为余数答案。
| $n$ | $rem \times (x^a \odot p)$ | $rem_n=rem_{n-1} \times x_{n-1} \odot p$ | $x_n=x_{n-1}^2 \odot p$ | $a_n=a_{n-1}//2$ |
|---|---|---|---|---|
| $1$ | $1 \times (3^{19} \odot p)$ | $1$ | $3$ | $19$ |
| $2$ | $3 \times (9^{9} \odot p)$ | $3=1\times3\odot p$ | $9=3^2 \odot p$ | $9=19//2$ |
| $3$ | $27 \times (81^{4} \odot p)$ | $27 = 3 \times 9 \odot p$ | $81=9^2\odot p$ | $4=9//2$ |
| $4$ | $27 \times (6561^{2} \odot p)$ | $27$ | $6561=81^2 \odot p$ | $2=4//2$ |
| $5$ | $27 \times (43046721^{1} \odot p)$ | $27$ | $43046721=6561^2 \odot p$ | $1=2//2$ |
| $6$ | $162261460 \times (175880701^{0} \odot p)$ | $162261460=27 \times 43046721 \odot p$ | $175880701=43046721^2 \odot p$ | $0=1//2$ |
Python 代码： 由于语言特性，理论上 Python 中的变量取值范围由系统内存大小决定（无限大），因此在 Python 中其实不用考虑大数越界问题。
Java/C++ 代码： 根据二分法计算原理，至少要保证变量 x 和 rem 可以正确存储 $1000000007^2$ ，而 $2^{64} > 1000000007^2 > 2^{32}$ ，因此我们选取 long 类型。
class Solution:
def cuttingBamboo(self, bamboo_len: int) -> int:
if bamboo_len <= 3: return bamboo_len - 1
a, b, p, x, rem = bamboo_len // 3 - 1, bamboo_len % 3, 1000000007, 3 , 1
while a > 0:
if a % 2: rem = (rem * x) % p
x = x ** 2 % p
a //= 2
if b == 0: return (rem * 3) % p # = 3^(a+1) % p
if b == 1: return (rem * 4) % p # = 3^a * 4 % p
return (rem * 6) % p # = 3^(a+1) * 2 % p
class Solution {
public int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) return bamboo_len - 1;
int b = bamboo_len % 3, p = 1000000007;
long rem = 1, x = 3;
for(int a = bamboo_len / 3 - 1; a > 0; a /= 2) {
if(a % 2 == 1) rem = (rem * x) % p;
x = (x * x) % p;
}
if(b == 0) return (int)(rem * 3 % p);
if(b == 1) return (int)(rem * 4 % p);
return (int)(rem * 6 % p);
}
}
class Solution {
public:
int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) return bamboo_len - 1;
int b = bamboo_len % 3, p = 1000000007;
long rem = 1, x = 3;
for(int a = bamboo_len / 3 - 1; a > 0; a /= 2) {
if(a % 2 == 1) rem = (rem * x) % p;
x = (x * x) % p;
}
if(b == 0) return (int)(rem * 3 % p);
if(b == 1) return (int)(rem * 4 % p);
return (int)(rem * 6 % p);
}
};
# 由于语言特性，Python 可以不考虑大数越界问题
class Solution:
def cuttingBamboo(self, bamboo_len: int) -> int:
if bamboo_len <= 3: return bamboo_len - 1
a, b, p = bamboo_len // 3, bamboo_len % 3, 1000000007
if b == 0: return 3 ** a % p
if b == 1: return 3 ** (a - 1) * 4 % p
return 3 ** a * 2 % p
以下为 二分求余法 的复杂度。