Блог пользователя Son_Nguyen

Sum of exponential
Автор Son_Nguyen, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Check Div1-500 here.

→ Ответить