Mamedov's blog

One problem from Number theory
By Mamedov, history, 8 years ago, In English

How to calculate ?

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

Please can someone help?

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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.

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

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.

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

Specifying the time constraint would be nice. :)

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

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

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

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

→ Reply