rahulpadhy's blog

SPOJ EASYFACT
By rahulpadhy, history, 8 years ago, In English

Can anyone tell me how to approach this question ? I have been trying it for quite sometime now, but to no avail.. The link to the question is : http://www.spoj.com/problems/EASYFACT/

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

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

Any sum of consecutive integers can be described by a low value a and a length r. So we must have:

Try simplifying this expression and then factoring it.

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

    Can you please explain this one a bit more ? I had got this expression, but unable to proceed any further..

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

      Sure. To get that first formula, notice that

      Simplifying the formula in my previous comment, we get

      2N! = r(r + 2a + 1).

      Instead of counting all pairs (r,a) we will count all pairs (r,r+2a+1) because it's simpler: now we're just counting all ordered pairs (x,y) with xy = 2N! where x<y and x and y have different parity.

      This is equivalent to counting the number of odd divisors of 2N!. I can explain the solution to this reduced problem if you're still stuck.

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

        Suppose that I consider n = 5. Now if I am counting the number of odd divisors of (2 * 5 !), then I am getting the odd divisors as (1, 3, 5, 15), which is 4. But in the question, we can see that the answer for n = 5 is 2, i.e., when we are considering the sum of 3 consecutive positive integers(39 + 40 + 41) and the sum of 5 consecutive positive integers(22 + 23 + 24 + 25 + 26). So still stuck..

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          Since we have to remove the case when r=1, we must subtract 1 from the final answer (so for n=5, we get 3). The answer for n=5 should be 3, since we also have the sum of 15 consecutive positive integers (120 = 1 + 2 + ... + 14 + 15).

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

        .

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

        This may be sound silly but how did you concluded that "This is equivalent to counting odd divisors of 2N!"

        → Reply