c++快速幂中的语言问题

身份认证VIP会员低至7折

温馨提示:虛拟产品一经售出概不退款

一个资源只可评论一次评论内容不能少于5个字

不错,但是能运算的大数不是很大

  已知底数a指数b,取模值mo


二、朴素算法(已知可跳过)

  时间复杂度O(b)  


   先讨论无需取模的

  所以我们可以如此迭代下去

  指数为10 是一个偶数,则底数2平方指数变为一半 [ ①→② ]

  指数为5 是一个奇数,则先将底数提出作为系数(22)此时指数为4 是一个偶数,则底数22再平方指数再变为一半 [ ②→③ ]

  不断迭代下去,当指数为1时则直接得出答案

  最后只要将每次相乘时取模即可,时间复杂度O(log2b)

版权所有转载请联系作者,违者必究

我要回帖

更多关于 幂等处理 的文章

 

随机推荐