题目描述

https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vcapc/
image.png

解题思路

本题和上一题最大的区别就是唯一不同在于本题目涉及 大数越界情况下的求余问题 。

循环取余

分成每段长度为3的绳子乘积最大，考虑到取模问题，自定义一个求幂方法，每次循环进行乘法时都进行一次取模，避免越界。

  1. class Solution {
  2.     // 循环求余法，每计算一次求一次余数
  3.     public long pow(long n, long m) {
  4.         long ans = 1;
  5.         for(int i = 0; i < m; i++) {
  6.             ans = ans * n % 1000000007;
  7.         }
  9.         return ans;
  10.     }
  12.     public int cuttingRope(int n) {
  13.         if (n <= 3) return n - 1;
  14.         int i = n / 3;
  15.         int j = n % 3;
  16.         long ans = 0;
  17.         if (j == 0) ans = pow(3, i);
  18.         if (j == 1) ans = pow(3, i - 1) * 4 % 1000000007;
  19.         if (j == 2) ans = pow(3, i) * 2 % 1000000007;
  20.         return (int) ans;
  21.     }
  22. }

快速幂

参照：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vbrri/