# POJ2140

Written by    12:01 September 17, 2014

POJ2140

Herd Sums
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16949 Accepted: 9987

Description

The cows in farmer John’s herd are numbered and branded with consecutive integers from 1 to N (1 <= N <= 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N.

Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7+8, 4+5+6, and 1+2+3+4+5.

When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10.

Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem.

Input

* Line 1: A single integer: N

Output

* Line 1: A single integer that is the number of ways consecutive cow brands can sum to N.

Sample Input

Sample Output

Source

AC很简单，但是关键就在于怎么提高时间效率

329MS必然还有一大堆可以优化的地方，完了一看那个题目的status，一大片的0MS，然后在讨论区看了一下，发现这题目里面居然还有点门道

num=a+a+1+a+2+a+3+…+a+k

=(k+1)a+k(k+1)/2

=(k+1)(a+k/2)

Category : acmstudy

Tags :