最近改变刷题思路，开始跟Stanford的CS97SI来刷POJ，这样的话感觉比单纯地按照题目分类来刷更有效率一点
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 16949 | Accepted: 9987 |
Description
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
Output
Sample Input
|
1 |
15 |
Sample Output
|
1 |
4 |
Source
这道题目是一道非常有意思的题目，输入一个数num，可以由ans组N个连续数相加而成(N>=1)
比如15就可以=1+2+3+4+5或者4+5+6或者7+8或者15
AC很简单，但是关键就在于怎么提高时间效率
一开始我就是暴力枚举
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
for(int i = 1; i < = num/2; i++) { //i是相加的数的个数 if(i%2 == 1) //i为奇数的时候只要i能够被整除并且num/i所得到的中间值大于num/2即可 { if(num%i == 0 && (num/i>(i/2))) { ans++; } } else // i为偶数的时候，平均数肯定是0.5的奇数倍 { if((num/i*i+i/2) == num && (num/i >= i/2)) { ans++; } } } |
然后Submit的结果是
|
1 |
Accepted 748K 329MS G++ |
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)
因为k/2必然为整数，故k必然是偶数，所以k+1必然为奇数，所以这到题目就是求num的奇因子个数！
|
1 2 3 4 5 6 7 |
for(int i = 1; i < = num; i+=2) { if(num%i=0) { ans++; } } |
但是出来的结果却却是
|
1 |
Accepted 748K 250MS G++ |
看来还能继续优化，虽然非常想自己能够在JAVA课上想出来，可是遗憾的是最后依旧只能学习别人的代码
|
1 2 3 4 5 6 7 8 9 |
//公式: //(k+1)*a+k*(k+1)/2 int sum = 0; for(int i = 0; sum < = num; i++) { sum += i; if((num-sum) % (i+1) == 0 && (num-sum)/(i+1) !=0) ans++; } |
|
1 |
Accepted 752K 0MS G++ |
终于0MS！