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

One problem from Number theory
Автор Mamedov, история, 8 лет назад, По-английски

How to calculate ?

Constraints are 1 ≤ N, M ≤ 2 * 109, 1 ≤ x ≤ 50 and time limit is 1 second.

Please can someone help?

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

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

Auto comment: topic has been updated by Mamedov (previous revision, new revision, compare).

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

An O(x^2) solution is described here: https://www.hackerrank.com/contests/infinitum-mar14/challenges/summing-the-k-n-r-series

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

    In our case modulo M is not a prime, it can be any number, but by this way we will need to calculate modular inverse.

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

It can be solved using "divide and conquer" approach.

Assume you try to calculate

In the last sum

(l + k)x = lx + Cx1l(x - 1)k + ... + kx

It's clear that it's need to calculate sums

for all t from 0 to x to calculate the above sum.

Than use "divide and conquer" approach to calculate all this sums for N, first calculate this sums for N/2 and than use the above formulas to calculate sums for N.

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

Specifying the time constraint would be nice. :)

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

Auto comment: topic has been updated by Mamedov (previous revision, new revision, compare).

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

In what judge is this problem available? i would like to test my code.

→ Ответить