math - 权力总和

Question

我必须编写代码来评估以下序列的值：

( pow(1,k) + pow(2,k) + ... + pow(n,k) ) % MOD 对于给定的 n、k 和 MOD 值。

我试过在互联网上搜索它。我有一个方程。它包含 zeta 函数，实施起来似乎很困难。我想要任何简单的方法来实现它。请注意，n 的值很大，因此我们不能简单地使用暴力破解时间限制。

Answer 1

只使用 Python

k=input("Enter value for K: ")
n=input("Enter value for N: ")
mod=input("Enter value for MOD: ")
sum=0
for i in range(1,n+1):
    sum+=pow(i,k)
result=sum % mod
print mod

可能这段代码会有所帮助。

Answer 2

牛顿的身份可能会有所帮助。计算以 1..n 为根的多项式的系数。那很琐碎。然后使用身份。

当我看到幂的总和时，这只是我想到的第一件事。

我认为它与模运算很好地兼容——只有乘法和加法。

我必须承认，牛顿的恒等式只是术语的重新排列，所以这里没有太多的速度增益。

Answer 3

我同意 math.stackexchange.com 是一个更好的选择。

但这里有一些随机事实，根据参数，可能会使问题更易于管理。

首先，因数MOD，求解每个素数功率因数，然后使用中国剩余定理找到 的答案MOD。因此，不失一般性，您可以假设 MOD 是主要力量。

接下来，请注意1^k + ... + MOD^k总是能被 整除MOD。因此，您可以替换n为n mod MOD。

接下来，如果MOD = p^iandj不能被 整除p，那么j^((p-1) * p^(i-1))是1mod MOD，所以我们可以减小 的大小k。

当然，如果(k, n) < MOD和MOD是素数，这根本不会帮助你。（这取决于这个问题是如何出现的，很可能就是这种情况。）

（如果k足够小，您可以为总和生成明确的公式。但对于您来说，似乎k可以足够大以使该方法难以处理。）