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/
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/
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
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.
Can you please explain this one a bit more ? I had got this expression, but unable to proceed any further..
Sure. To get that first formula, notice that
Simplifying the formula in my previous comment, we get
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.
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..
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).
.
This may be sound silly but how did you concluded that "This is equivalent to counting odd divisors of 2N!"