首页 > 其他 > 详细

自然数幂和取模问题进一步探究

时间:2014-10-10 02:01:53      阅读:317      评论:0      收藏:0      [点我收藏+]

在上次的文章 http://blog.csdn.net/acdreamers/article/details/38929067 中,学习了求自然数幂

和的有效方法,并且了解了求伯努利数的优美算法。今天,我们来看两个简单的问题。

 

问题:bubuko.com,布布扣的值,满足bubuko.com,布布扣bubuko.com,布布扣bubuko.com,布布扣

 

分析:很容易看出连续bubuko.com,布布扣个数的结果是相同的,即循环节长度为bubuko.com,布布扣,对于bubuko.com,布布扣,需要先进行降幂,所用公式如下

 

      bubuko.com,布布扣

 

     最坏时间复杂度约为bubuko.com,布布扣

 

 

问题:bubuko.com,布布扣的值。其中bubuko.com,布布扣bubuko.com,布布扣,并且bubuko.com,布布扣是奇数。

 

分析:首先,我们来关注bubuko.com,布布扣。由

 

     bubuko.com,布布扣

     

     到了这里,由于bubuko.com,布布扣是奇数,那么bubuko.com,布布扣

 

    (1)如果bubuko.com,布布扣为奇数,则刚好全部抵消,答案就是0

    (2)如果bubuko.com,布布扣为偶数,则最后剩余中间那一项,即答案为bubuko.com,布布扣

 

 

 

自然数幂和取模问题进一步探究

原文:http://blog.csdn.net/acdreamers/article/details/39941387

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!