14- II. 剪绳子 II,取模
文章目录
14- II. 剪绳子 II

思路:
与14- I. 剪绳子相比,多了取模。
由于最后结果以指数形式增长,可能会超int32 甚至int64,
若只在最终结果求余:
因此需要逐步求余,求余具有结论如下:
(xy)%p = [(x%p)(y%p)]%p
(x^a)%p = ((···(x%p)*x%p)····*x%p)因此采用循环求余的方法:
每乘一次3,取一次模,最后return再取一次模。
操作:

官方:
n=4没有操作,可以优化掉
注意:
- 最终结果res用long型来接收
- 最终return res*n%1000000007,就考虑了余数为0,1,2以及4的情况。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论