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

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

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

 

问题：求的值，满足，和。

 

分析：非常easy看出连续个数的结果是同样的，即循环节长度为，对于，须要先进行降幂，所用公式例如以下

 

     

 

     最坏时间复杂度约为。

 

 

问题：求的值。当中和，而且是奇数。

 

分析：首先，我们来关注。由

 

     

     

     到了这里，因为是奇数，那么。

 

    （1）假设为奇数，则刚好所有抵消，答案就是0。

    （2）假设为偶数，则最后剩余中间那一项，即答案为。