Son_Nguyen's blog

Sum of exponential
By Son_Nguyen, history, 10 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

»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Check Div1-500 here.

→ Reply