三个月算法进阶--day53
目录
快速幂
** / pow() O(log n)
浮点取幂
math.pow() O(1)
大数求余
循环取余O(n)、快速幂求余O(log n)
res = 1
while n:
if n % 2:
res = (res * base) % p
base = base ** 2 % p
n //= 2
剪绳子（数学推导）
每段为e，乘积最大
class Solution:
def cuttingRope(self, n: int) -> int:
if n <=3:
return n-1
a, b = n // 3, n % 3
if b == 0:
return int(math.pow(3, a))
elif b == 1:
return int(math.pow(3, a-1)) * 4
else:
return int(math.pow(3, a)) * 2