0

I am using python pow(n,k,mod) to get the power sum of natural numbers, but not getting perfect time complexity. what i used

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

can u suggest any aglorithmic approach to solve power sum 

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

where k ranges from 1 to 1000 and n belong to natural number 1

Spektre
  • 49,595
  • 11
  • 110
  • 380
rakesh kumar
  • 11
  • 3
  • 1
    And what is the perfect time complexity in your opinion? Show the code that you used. – Nico Schertler Nov 18 '17 at 08:32
  • @NicoSchertler I got the feeling from the equation that it could possibly be solved by some FFT approach What do you think (You seem to have more experience in this field)? – Spektre Nov 18 '17 at 08:43
  • 1
    I see the edit so the equation is `1^k + ... + n^k mod 1000000009` (I edited your question with it so if not the case edit it back). So you do not need `bigints`. As it is ongoing contest then just hint for speedup: you should decompose the therms so you can compute non prime `i` from prime `i` to significantly lower the count of multiplications needed.... Also you should start with `total = 1` as you skip `1^k` in the `for` loop – Spektre Nov 18 '17 at 09:09
  • Possible duplicate of [Calculating 1^X + 2^X + ... + N^X mod 1000000007](https://stackoverflow.com/questions/41695283/calculating-1x-2x-nx-mod-1000000007) – tobias_k Nov 20 '17 at 21:45

1 Answers1

1

You can use dynamic programming to avoid recalculation of large powers. For example 16^k is (2^k)^4. You already calculated 2^k so you can lookup it in a table, or --using a look-ahead strategy-- you can calculate all powers of say 2 beforehand.

sorush-r
  • 10,490
  • 17
  • 89
  • 173