總和的權力

Question

我必須代碼評估下列順序的價值：

(pow(1,k) + pow(2,k) + ... + pow(n,k)) % MOD 爲N，K和MOD的給定值。

我試過在internet上搜索它。我得到了一個等式。它包含zeta函數，在實現中似乎很難。我想要實現相同的任何簡單的方法。請注意，n的值很大，所以我們不能簡單地使用蠻力來通過時間限制。

Answer 1

Newton's identities可能有幫助。計算1..n作爲根的多項式的係數。那很瑣碎。然後使用身份。

這只是當我看到權力的總和時想到的第一件事。

我認爲它與模塊化算法很好地兼容 - 只有乘法和補充。我必須承認，牛頓的身份只是條款的重新排列，所以在這裏沒有太多的速度增益。

Answer 2

我同意math.stackexchange.com是一個更好的選擇。

但是，這裏是隨機的事實，根據參數，可能會使問題更易於管理。

首先，因子MOD，求解每個素數的功率因子，然後用中國剩餘定理找到答案爲MOD。因此，在不失一般性的情況下，您可以假設MOD是一種主要力量。

接下來，請注意，1^k + ... + MOD^k總是可以被MOD整除。因此，您可以用n mod MOD替換n。

接下來，如果MOD = p^i和j是不是p整除，那麼j^((p-1) * p^(i-1))是1國防部MOD，所以我們可以減少k大小。

當然，如果(k, n) < MOD和MOD是首要的，這對你根本沒有任何幫助。 （這取決於這個問題如何發生，很可能是這種情況。）

（如果k足夠小，那麼可以爲總和生成明確的公式，但似乎對於您而言，k可能很大足以使這種方法難以解決。）

Answer 3

JUST使用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 

可能是這個代碼是要去幫助。