求自然数幂和的算法

Question

我正在使用 python pow(n,k,mod) 来获取自然数的幂和，但没有获得完美的时间复杂度。我用了什么

mod = 10**9+9
total = 0
for i in range(2, n):
    x = pow(i, k, mod)
    total += x
    total = total%mod
return total

你能建议任何求解幂和的算法吗

( 1^k + 2^k + 3^k + 4^k .... n^k ) mod 1000000009

其中k的取值范围为1到1000，n为自然数1

Answer 1

您可以使用 dynamic programming以避免重新计算大幂次。例如 16^k 是 (2^k)^4。您已经计算了 2^k，因此您可以在表中查找它，或者——使用前瞻策略——您可以预先计算出 say 2 的所有幂。