小编ank*_*ker的帖子

所以我遇到了这个需要计算的问题:

1 ^k +(1 + p)^k +(1 + 2*p)^k + ..... +(1 + n*p)^k%p

其中p是素数,k是严格小于p的某个数.

p小于500,n*p的范围可达10 ⁹

我能想到的唯一解决方案是从第一个术语到最后一个术语进行迭代,并使用取幂来计算模数,但这样做太昂贵了我正在寻找更快的算法.

是否可以更快地完成？