LeetCode-Book 详解剑指 Offer 14-II 剪绳子 II基于均值不等式的切分策略与大数求余快速幂取模【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库中《剑指 Offer》部分的 剑指 Offer 14- II. 剪绳子 II 解析文档系统讲解剪绳子 II这道经典的数学推导型动态规划变形题如何通过算术几何均值不等式证明尽可能等分为 3是最优切分策略以及当n很大时如何用循环求余与快速幂求余在int范围内安全计算3^a % 1000000007。读完后你将掌握完整的数学推导链条、三种余数情形的切分规则以及 Python / Java / C 三种语言的参考实现细节。问题背景与剪绳子 I的关系本题与 剑指 Offer 14- I. 剪绳子 主体等价唯一不同在于本题目涉及大数越界情况下的求余问题原书建议先做上一道题其参考实现见 sfo_14i_cut_the_rope_i_s1.py在此基础上再研究本题的大数求余方法。题目的数学本质是设将长度为 $n$ 的绳子切为 $a$ 段$$ n n_1 n_2 ... n_a $$本题等价于求解各段长度的最大乘积$$ \max(n_1 \times n_2 \times ... \times n_a) $$并且由于本题结果可能极大最终需要对质数模数 $p 1000000007$ 取余返回。数学推导为什么最优切段长度是 3原书的推导总体分为两步① 当所有绳段长度相等时乘积最大② 最优的绳段长度为 $3$。推论一等分多段时乘积最大依据算术几何均值不等式等号当且仅当 $n_1 n_2 ... n_a$ 时成立$$ \frac{n_1 n_2 ... n_a}{a} \geq \sqrt[a]{n_1 n_2 ... n_a} $$推论一将绳子以相等的长度等分为多段得到的乘积最大。推论二最优段长为 3而非 2设将绳子按照 $x$ 长度等分为 $a$ 段即 $n ax$则乘积为 $x^a$。由于 $n$ 为常数因此当 $x^{\frac{1}{x}}$ 取最大值时乘积达到最大值$$ x^a x^{\frac{n}{x}} (x^{\frac{1}{x}})^n $$问题转化为求 $y x^{\frac{1}{x}}$ 的极大值对 $x$ 求导$$ \begin{aligned} \ln y \frac{1}{x} \ln x \text{取对数} \ \frac{1}{y} \dot {y} \frac{1}{x^2} - \frac{1}{x^2} \ln x \text{对 $x$ 求导} \ \frac{1 - \ln x}{x^2} \ \dot {y} \frac{1 - \ln x}{x^2} x^{\frac{1}{x}} \text{整理得} \end{aligned} $$令 $\dot {y} 0$得 $1 - \ln x 0$驻点为 $x_0 e \approx 2.7$。由导数符号变化可知 $x_0$ 为极大值点$$ \dot {y} \begin{cases}0 , x \in [- \infty, e) \ 0 , x \in (e, \infty] \end{cases} $$由于切分长度 $x$ 必须为整数最接近 $e$ 的整数为 $2$ 或 $3$。代入对比$$ y(3) 3^{1/3} \approx 1.44, \quad y(2) 2^{1/2} \approx 1.41 $$口算对比技巧给两数字同时取 $6$ 次方再对比$$ [y(3)]^6 (3^{1/3})^6 9 [y(2)]^6 (2^{1/2})^6 8 $$推论二尽可能将绳子以长度 $3$ 等分为多段时乘积最大。切分规则与算法流程综合两条推论原书给出按优先级排列的切分规则最优$3$。把绳子尽可能切为多个长度为 $3$ 的片段留下的最后一段绳子长度可能为 $0$、$1$、$2$ 三种情况次优$2$。若最后一段绳子长度为 $2$则保留不再拆为 $11$最差$1$。若最后一段绳子长度为 $1$则应把一份 $3 1$ 替换为 $2 2$因为 $2 \times 2 3 \times 1$。据此算法流程分为两个分支设求余操作符号为 $\odot$分支 1$n \leq 3$。按照规则本应不切分但题目要求必须剪成 $m 1$ 段因此必须剪出一段长度为 $1$ 的绳子直接返回 $n - 1$即cuttingRope(2) 1、cuttingRope(3) 2。分支 2$n 3$。求 $n$ 除以 $3$ 的整数部分 $a$ 和余数部分 $b$即 $n 3a b$分三种情况处理余数 $b$切分形态返回结果$0$$a$ 段长度为 $3$$3^a \odot 1000000007$$1$一个 $13$ 转换为 $22$$(3^{a-1} \times 4) \odot 1000000007$$2$$a$ 段长度为 $3$另留一段 $2$$(3^a \times 2) \odot 1000000007$以仓库测试用例n 10验证$10 3 \times 3 1$触发 $b1$ 情形切分为 $3 3 4$乘积 $3 \times 3 \times 4 36$三种语言实现的驱动代码均以该输入运行并输出36见下文源码部分。大数求余本题真正的难点为什么需要大数求余大数越界当 $a$ 增大时最终返回的 $3^a$ 以指数级别增长可能超出int32甚至int64的取值范围导致返回值错误大数求余问题在仅使用int32类型存储的前提下正确计算 $x^a$ 对 $p$ 求余即 $x^a \odot p$的值解决方案循环求余、快速幂求余。后者时间复杂度更低两种方法均基于以下求余运算规则推出$$ (xy) \odot p [(x \odot p)(y \odot p)] \odot p $$方法一循环求余时间复杂度 O(N)根据求余运算性质推出因为本题中 $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$为循环的线性复杂度。方法二快速幂求余时间复杂度 O(log N)根据求余运算性质可推出$$ 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帮助理解原书示例表格初始状态 $rem1, x3, a19, p1000000007$循环将 $rem \times (x^a \odot p)$ 逐步化为 $rem \times (x^0 \odot p) rem \times 1$ 的形式即rem为余数答案$n$$rem \times (x^a \odot p)$$rem_nrem_{n-1} \times x_{n-1} \odot p$$x_nx_{n-1}^2 \odot p$$a_na_{n-1}//2$$1$$1 \times (3^{19} \odot p)$$1$$3$$19$$2$$3 \times (9^{9} \odot p)$$31\times3\odot p$$93^2 \odot p$$919//2$$3$$27 \times (81^{4} \odot p)$$27 3 \times 9 \odot p$$819^2\odot p$$49//2$$4$$27 \times (6561^{2} \odot p)$$27$$656181^2 \odot p$$24//2$$5$$27 \times (43046721^{1} \odot p)$$27$$430467216561^2 \odot p$$12//2$$6$$162261460 \times (175880701^{0} \odot p)$$16226146027 \times 43046721 \odot p$$17588070143046721^2 \odot p$$01//2$参考实现三种语言的完整代码原书特别指出了语言差异这一工程细节Python由于语言特性理论上变量取值范围由系统内存大小决定无限大其实不需要考虑大数越界问题Java / C根据快速幂计算原理至少要保证变量x和rem可以正确存储 $1000000007^2$而 $2^{64} 1000000007^2 2^{32}$因此必须选取long类型long为 64 位乘法中间量才不会溢出。Python快速幂求余版这是原书主推的带求余过程写法仓库实现sfo_14ii_cut_the_rope_ii_s1.py。一个值得注意的实现技巧是循环的指数取a n // 3 - 1比数学推导少 1 个 3把最后一段 $3^1$ 留到循环外与余数部分合并处理——这样循环结束后rem 3^{n//3 - 1} % p三种余数情形分别再乘3、4、6即可class Solution: def cuttingRope(self, n: int) - int: if n 3: return n - 1 a, b, p, x, rem n // 3 - 1, n % 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^(a1) % p if b 1: return (rem * 4) % p # 3^a * 4 % p return (rem * 6) % p # 3^(a1) * 2 % p仓库中该文件的驱动代码以n 10为测试用例可直接运行验证输出36。Python利用大整数特性的简化版仓库另一实现sfo_14ii_cut_the_rope_ii_s2.py利用 Python 大整数直接3 ** a后取余逻辑与切分规则一一对应可读性更强# 由于语言特性Python 可以不考虑大数越界问题 class Solution: def cuttingRope(self, n: int) - int: if n 3: return n - 1 a, b, p n // 3, n % 3, 1000000007 if b 0: return 3 ** a % p if b 1: return 3 ** (a - 1) * 4 % p return 3 ** a * 2 % pJava / Clong 防溢出版两语言实现几乎逐行一致仓库实现Java 版、C 版核心是long rem 1, x 3两个 64 位变量承载x * x最大约 $10^{18} 2^{63}$这类中间乘积class Solution { public int cuttingRope(int n) { if(n 3) return n - 1; int b n % 3, p 1000000007; long rem 1, x 3; for(int a n / 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 cuttingRope(int n) { if(n 3) return n - 1; int b n % 3, p 1000000007; long rem 1, x 3; for(int a n / 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); } };从源码结构看Java 与 C 版本均使用for (int a n / 3 - 1; a 0; a / 2)的 for 循环形态等价替代 Python 的while快速幂骨架语义完全一致。复杂度分析以下为快速幂二分求余法的复杂度结论与原书一致时间复杂度 $O(\log_2 N)$其中 $N a$。二分法为对数级别复杂度每轮仅有求整、求余、次方运算。原书引用公开资料认为不超过机器字长的整数的求整/求余运算可视为 $O(1)$整型取幂在快速幂中退化为单次乘法同理视为 $O(1)$空间复杂度 $O(1)$变量a, b, p, x, rem使用常数大小的额外空间。小结与延伸阅读本题的解题链条可以概括为均值不等式证明等分最优 → 求导得到 $e \approx 2.7$ → 整数约束下比较 $2^{1/2}$ 与 $3^{1/3}$ 锁定段长 3 → 按余数 0/1/2 处理尾段31 → 22的关键替换→ 快速幂取模保证大数安全。其中 $b 1$ 时借一个 3 凑成 22的处理是本算法最容易出错的细节建议结合 $n \in {2, 3, 4, 5, 7, 10}$ 等边界样例逐一验证。在 LeetCode-Book 仓库中本篇的完整解析文档位于 sword_for_offer/docs/剑指 Offer 14- II. 剪绳子 II.md前置题目 剑指 Offer 14- I. 剪绳子 的数学推导部分与本文同源可作为对照阅读三种语言的完整可运行实现分别存放在sword_for_offer/codes/python/、sword_for_offer/codes/java/、sword_for_offer/codes/cpp/目录下均附带n 10的驱动测试代码可直接编译运行复核上述推导。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Book 详解剑指 Offer 14-II 剪绳子 II：基于均值不等式的切分策略与大数求余（快速幂取模）
LeetCode-Book 详解剑指 Offer 14-II 剪绳子 II基于均值不等式的切分策略与大数求余快速幂取模【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库中《剑指 Offer》部分的 剑指 Offer 14- II. 剪绳子 II 解析文档系统讲解剪绳子 II这道经典的数学推导型动态规划变形题如何通过算术几何均值不等式证明尽可能等分为 3是最优切分策略以及当n很大时如何用循环求余与快速幂求余在int范围内安全计算3^a % 1000000007。读完后你将掌握完整的数学推导链条、三种余数情形的切分规则以及 Python / Java / C 三种语言的参考实现细节。问题背景与剪绳子 I的关系本题与 剑指 Offer 14- I. 剪绳子 主体等价唯一不同在于本题目涉及大数越界情况下的求余问题原书建议先做上一道题其参考实现见 sfo_14i_cut_the_rope_i_s1.py在此基础上再研究本题的大数求余方法。题目的数学本质是设将长度为 $n$ 的绳子切为 $a$ 段$$ n n_1 n_2 ... n_a $$本题等价于求解各段长度的最大乘积$$ \max(n_1 \times n_2 \times ... \times n_a) $$并且由于本题结果可能极大最终需要对质数模数 $p 1000000007$ 取余返回。数学推导为什么最优切段长度是 3原书的推导总体分为两步① 当所有绳段长度相等时乘积最大② 最优的绳段长度为 $3$。推论一等分多段时乘积最大依据算术几何均值不等式等号当且仅当 $n_1 n_2 ... n_a$ 时成立$$ \frac{n_1 n_2 ... n_a}{a} \geq \sqrt[a]{n_1 n_2 ... n_a} $$推论一将绳子以相等的长度等分为多段得到的乘积最大。推论二最优段长为 3而非 2设将绳子按照 $x$ 长度等分为 $a$ 段即 $n ax$则乘积为 $x^a$。由于 $n$ 为常数因此当 $x^{\frac{1}{x}}$ 取最大值时乘积达到最大值$$ x^a x^{\frac{n}{x}} (x^{\frac{1}{x}})^n $$问题转化为求 $y x^{\frac{1}{x}}$ 的极大值对 $x$ 求导$$ \begin{aligned} \ln y \frac{1}{x} \ln x \text{取对数} \ \frac{1}{y} \dot {y} \frac{1}{x^2} - \frac{1}{x^2} \ln x \text{对 $x$ 求导} \ \frac{1 - \ln x}{x^2} \ \dot {y} \frac{1 - \ln x}{x^2} x^{\frac{1}{x}} \text{整理得} \end{aligned} $$令 $\dot {y} 0$得 $1 - \ln x 0$驻点为 $x_0 e \approx 2.7$。由导数符号变化可知 $x_0$ 为极大值点$$ \dot {y} \begin{cases}0 , x \in [- \infty, e) \ 0 , x \in (e, \infty] \end{cases} $$由于切分长度 $x$ 必须为整数最接近 $e$ 的整数为 $2$ 或 $3$。代入对比$$ y(3) 3^{1/3} \approx 1.44, \quad y(2) 2^{1/2} \approx 1.41 $$口算对比技巧给两数字同时取 $6$ 次方再对比$$ [y(3)]^6 (3^{1/3})^6 9 [y(2)]^6 (2^{1/2})^6 8 $$推论二尽可能将绳子以长度 $3$ 等分为多段时乘积最大。切分规则与算法流程综合两条推论原书给出按优先级排列的切分规则最优$3$。把绳子尽可能切为多个长度为 $3$ 的片段留下的最后一段绳子长度可能为 $0$、$1$、$2$ 三种情况次优$2$。若最后一段绳子长度为 $2$则保留不再拆为 $11$最差$1$。若最后一段绳子长度为 $1$则应把一份 $3 1$ 替换为 $2 2$因为 $2 \times 2 3 \times 1$。据此算法流程分为两个分支设求余操作符号为 $\odot$分支 1$n \leq 3$。按照规则本应不切分但题目要求必须剪成 $m 1$ 段因此必须剪出一段长度为 $1$ 的绳子直接返回 $n - 1$即cuttingRope(2) 1、cuttingRope(3) 2。分支 2$n 3$。求 $n$ 除以 $3$ 的整数部分 $a$ 和余数部分 $b$即 $n 3a b$分三种情况处理余数 $b$切分形态返回结果$0$$a$ 段长度为 $3$$3^a \odot 1000000007$$1$一个 $13$ 转换为 $22$$(3^{a-1} \times 4) \odot 1000000007$$2$$a$ 段长度为 $3$另留一段 $2$$(3^a \times 2) \odot 1000000007$以仓库测试用例n 10验证$10 3 \times 3 1$触发 $b1$ 情形切分为 $3 3 4$乘积 $3 \times 3 \times 4 36$三种语言实现的驱动代码均以该输入运行并输出36见下文源码部分。大数求余本题真正的难点为什么需要大数求余大数越界当 $a$ 增大时最终返回的 $3^a$ 以指数级别增长可能超出int32甚至int64的取值范围导致返回值错误大数求余问题在仅使用int32类型存储的前提下正确计算 $x^a$ 对 $p$ 求余即 $x^a \odot p$的值解决方案循环求余、快速幂求余。后者时间复杂度更低两种方法均基于以下求余运算规则推出$$ (xy) \odot p [(x \odot p)(y \odot p)] \odot p $$方法一循环求余时间复杂度 O(N)根据求余运算性质推出因为本题中 $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$为循环的线性复杂度。方法二快速幂求余时间复杂度 O(log N)根据求余运算性质可推出$$ 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帮助理解原书示例表格初始状态 $rem1, x3, a19, p1000000007$循环将 $rem \times (x^a \odot p)$ 逐步化为 $rem \times (x^0 \odot p) rem \times 1$ 的形式即rem为余数答案$n$$rem \times (x^a \odot p)$$rem_nrem_{n-1} \times x_{n-1} \odot p$$x_nx_{n-1}^2 \odot p$$a_na_{n-1}//2$$1$$1 \times (3^{19} \odot p)$$1$$3$$19$$2$$3 \times (9^{9} \odot p)$$31\times3\odot p$$93^2 \odot p$$919//2$$3$$27 \times (81^{4} \odot p)$$27 3 \times 9 \odot p$$819^2\odot p$$49//2$$4$$27 \times (6561^{2} \odot p)$$27$$656181^2 \odot p$$24//2$$5$$27 \times (43046721^{1} \odot p)$$27$$430467216561^2 \odot p$$12//2$$6$$162261460 \times (175880701^{0} \odot p)$$16226146027 \times 43046721 \odot p$$17588070143046721^2 \odot p$$01//2$参考实现三种语言的完整代码原书特别指出了语言差异这一工程细节Python由于语言特性理论上变量取值范围由系统内存大小决定无限大其实不需要考虑大数越界问题Java / C根据快速幂计算原理至少要保证变量x和rem可以正确存储 $1000000007^2$而 $2^{64} 1000000007^2 2^{32}$因此必须选取long类型long为 64 位乘法中间量才不会溢出。Python快速幂求余版这是原书主推的带求余过程写法仓库实现sfo_14ii_cut_the_rope_ii_s1.py。一个值得注意的实现技巧是循环的指数取a n // 3 - 1比数学推导少 1 个 3把最后一段 $3^1$ 留到循环外与余数部分合并处理——这样循环结束后rem 3^{n//3 - 1} % p三种余数情形分别再乘3、4、6即可class Solution: def cuttingRope(self, n: int) - int: if n 3: return n - 1 a, b, p, x, rem n // 3 - 1, n % 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^(a1) % p if b 1: return (rem * 4) % p # 3^a * 4 % p return (rem * 6) % p # 3^(a1) * 2 % p仓库中该文件的驱动代码以n 10为测试用例可直接运行验证输出36。Python利用大整数特性的简化版仓库另一实现sfo_14ii_cut_the_rope_ii_s2.py利用 Python 大整数直接3 ** a后取余逻辑与切分规则一一对应可读性更强# 由于语言特性Python 可以不考虑大数越界问题 class Solution: def cuttingRope(self, n: int) - int: if n 3: return n - 1 a, b, p n // 3, n % 3, 1000000007 if b 0: return 3 ** a % p if b 1: return 3 ** (a - 1) * 4 % p return 3 ** a * 2 % pJava / Clong 防溢出版两语言实现几乎逐行一致仓库实现Java 版、C 版核心是long rem 1, x 3两个 64 位变量承载x * x最大约 $10^{18} 2^{63}$这类中间乘积class Solution { public int cuttingRope(int n) { if(n 3) return n - 1; int b n % 3, p 1000000007; long rem 1, x 3; for(int a n / 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 cuttingRope(int n) { if(n 3) return n - 1; int b n % 3, p 1000000007; long rem 1, x 3; for(int a n / 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); } };从源码结构看Java 与 C 版本均使用for (int a n / 3 - 1; a 0; a / 2)的 for 循环形态等价替代 Python 的while快速幂骨架语义完全一致。复杂度分析以下为快速幂二分求余法的复杂度结论与原书一致时间复杂度 $O(\log_2 N)$其中 $N a$。二分法为对数级别复杂度每轮仅有求整、求余、次方运算。原书引用公开资料认为不超过机器字长的整数的求整/求余运算可视为 $O(1)$整型取幂在快速幂中退化为单次乘法同理视为 $O(1)$空间复杂度 $O(1)$变量a, b, p, x, rem使用常数大小的额外空间。小结与延伸阅读本题的解题链条可以概括为均值不等式证明等分最优 → 求导得到 $e \approx 2.7$ → 整数约束下比较 $2^{1/2}$ 与 $3^{1/3}$ 锁定段长 3 → 按余数 0/1/2 处理尾段31 → 22的关键替换→ 快速幂取模保证大数安全。其中 $b 1$ 时借一个 3 凑成 22的处理是本算法最容易出错的细节建议结合 $n \in {2, 3, 4, 5, 7, 10}$ 等边界样例逐一验证。在 LeetCode-Book 仓库中本篇的完整解析文档位于 sword_for_offer/docs/剑指 Offer 14- II. 剪绳子 II.md前置题目 剑指 Offer 14- I. 剪绳子 的数学推导部分与本文同源可作为对照阅读三种语言的完整可运行实现分别存放在sword_for_offer/codes/python/、sword_for_offer/codes/java/、sword_for_offer/codes/cpp/目录下均附带n 10的驱动测试代码可直接编译运行复核上述推导。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考