如何快速计算这个系列的模 m 的总和？
How to calculate sum of this series modulo m fast?
所以我遇到了这个问题，我需要计算这个：
1k+(1+p)k+(1+2*p)k+.....+(1+n*p)k % p
其中 p 是质数，k 是严格小于 p 的某个数。
p 小于 500，n*p 的范围可达 109
我能想到的唯一解决方案是从第一项到最后一项进行迭代，并使用求幂计算模数，但这样做的成本太高，我正在寻找一种更快的算法。
有没有可能做得更快？
对于任何整数 m, (1+m*p)^k % p == 1.
因此，计算
(1^k + (1+2*p)^k + (1+3*p)^k + ... + (1+n*p)^k )% p
与计算相同
(1 + 1 + 1 ... + 1) % p
括号内有n + 1项。
答案是(n + 1)%p。
所以我遇到了这个问题，我需要计算这个：
1k+(1+p)k+(1+2*p)k+.....+(1+n*p)k % p
其中 p 是质数，k 是严格小于 p 的某个数。
p 小于 500，n*p 的范围可达 109
我能想到的唯一解决方案是从第一项到最后一项进行迭代，并使用求幂计算模数，但这样做的成本太高，我正在寻找一种更快的算法。
有没有可能做得更快？
对于任何整数 m, (1+m*p)^k % p == 1.
因此，计算
(1^k + (1+2*p)^k + (1+3*p)^k + ... + (1+n*p)^k )% p
与计算相同
(1 + 1 + 1 ... + 1) % p
括号内有n + 1项。
答案是(n + 1)%p。