SPOJ.com - Problem SEQ6

SEQ6 - Consecutive sequence

#math

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

Input

The input file consists of multiple lines (about 10³ in the first data set and 10⁵ 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

Submit solution!

hide comments

< Previous 1 2 Next >

	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

Submit solution!

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