Son_Nguyen's blog

Sum of exponential
By Son_Nguyen, history, 9 years ago, In English

Hello, I have a problem need to solve:

S(n) = 1^k + 2^k +..+n^k

input: n<=10^9, k<=40

output: S(n)%(10^9+7).

One more issue:

how to calculate ((n^k)/x)%p which very big n and k.

Thank for helping me.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

See here for finding S(n). ((n^k)/x)%p = ((n^k)%(x*p))/x. Use binary exponentiation to evaluate (n^k)%(x*p).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy to prove that the answer is a polynomial with deg  ≤ k + 1. So you can find its coefficients using Gaussian elimination or any other way to interpolate it.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Easy to prove that the answer is a polynomial with deg  ≤ k + 1.

    how?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      For instance, using recurrent equation for sum of k-th powers through previous powers sums (see the link above).

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Check Div1-500 here.

→ Reply