SEQ6 - Consecutive sequence


We define consecutive sequence as a sequence of integer numbers {n, n+1, n+2, ..., n+m}. For each given positive integer N ≤ 107 calculate number of such sequences which sum is equal to N.

Input

The input file consists of multiple lines (about 103 in the first data set and 105 in the second), each line contains integer N. The input is terminated with N = 0, which should not be processed.

Output

Expected number in each line

Example

Input:

500
0

Output:

8

hide comments
Francky: 2014-12-07 16:10:01

This problem had been switched to cube since a while. Rejudge hadn't been done yet.

Rohan Phadke: 2014-10-12 07:55:37

A brilliant problem! Had SO much fun solving it! :D

Last edit: 2014-06-13 00:56:20
Francky: 2014-10-12 07:55:37

Excellent problem, (quite) strong cases.
But description is not exact : we are never told n is integer ; 249.5+250.5 == 500 and [249.5, 250.5] is a consecutive sequence of 'numbers'. The answer would be more than 8 for 500. (infinity for all N).
Should we modify it ?

RE: corrected, thank you

Last edit: 2014-10-12 07:56:02
pankaj bhardwaj: 2014-10-12 07:55:37

good question indeed
I have to wait for whole 1 day for that to come sqrt factor

Massand Sagar Sunil: 2014-10-12 07:55:37

Is m positive?

(Tjandra Satria Gunawan)(曾毅昆): 2014-10-12 07:55:37

"For each given positive integer N < 10^7 calculate number of such sequences which sum is equal to N."
i thing this is wrong, AC after increase limit for N to 10000001...

Re: thank you, corrected

Last edit: 2012-05-14 03:08:48
vipin: 2014-10-12 07:55:37

Why am I always getting tle? its O(sqrt(n)) algorithm..:(

Last edit: 2011-09-04 14:22:23
Gurpreet Singh: 2014-10-12 07:55:37

Any Hints!!!!!!!!
i am getting TLE always....
complexity being O(sqrt(n))

The Champ: 2014-10-12 07:55:37

i am getting TLE while my code gives answer within fractions of seconds. for 999999 my answer is 112, can someone give me a corner case..

RE (author): 128 is the right answer

Last edit: 2010-10-09 20:28:30

Added by:Ruslan Sennov
Date:2010-05-14
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6