Killever's blog

By Killever, 11 years ago, In English

On this Friday will take place Topcoder SRM 596.

GL & HF

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

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

How to solve the last problem efficiently?

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

How to solve 1000 div.2?

  • »
    »
    11 years ago, # ^ |
    Rev. 7   Vote: I like it +4 Vote: I do not like it

    At first you've to notice that for F(n) be divisible by P, at least one part of the multiplication (n — i²) must be a multiple of P. So we have that n — i² (mod P) = 0 (mod P), so n (mod P) = i² (mod P). It's clear that i must be less than sqrt(n), so we can iterate over all possible i's and for each of them count how many n's exists that are less than some integer A. After some math it's clear that counting this is equal to (A — i²)/P. That's not the complete solution, since we're overcalculating some n's, and this occurs when we have some positive integer j different from i and less than sqrt(n) such that j² (mod P) = i² (mod P). Using an array or a set to mark for each i if i² module P has been already visited is enough.

    Just calculate the answer for A being hi and subtract it from A being lo — 1 and you're done.

    P.S: To better explain why (A — i²)/P, we know that n (mod P) = i² (mod P) and we can express it as n = i² + P*k. We know that n must be less than A, so i² + P*k < A, so k is actually the number of different solutions. Isolating k, we have:

    P*k < A — i²

    k < (A — i²)/P


    k = floor((A — i²)/P)

    My code: http://pastie.org/private/gltsff0nslzgn6cyqdexa

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

      First Thanks for your neat explanation

      Second In inequality you say k < (A — i²)/P not k <= (A — i²)/P

      So what about if (A — i²)/P is integer like 12 so k<12 but

      floor(12) is 12

      So in this case k not less than (A — i²)/P but it equal to it

      Third I want to learn how to reduce problem to equations like this do you have any advice or a how can I practice on this ?

      Thanks

»
11 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it