Herd Sums
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 339 Accepted Submission(s): 162
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.
15
4
其实是水题的。结果我写的很复杂
因为考虑到如果用一重循环的话，势必会解方程。
我不喜欢解方程，于是写了一个二分查找来找方程的解
方法：枚举长度，二分起点
注意到数据量比较大
所以需要把数据变为__int64的
我的代码：
#include<stdio.h>
#include<string.h>
typedef __int64 ll;
ll m;
ll cal(ll s,ll x)
{
return (2*s+x-1)*x;
}
ll binary_search(ll x)
{
ll left,right,mid,tmp;
left=1,right=m/2+1;
while(left<=right)
{
mid=(left+right)>>1;
tmp=cal(mid,x);
if(tmp==2*m)
return mid;
else if(tmp<2*m)
left=mid+1;
else
right=mid-1;
}
return -1;
}
int main()
{
ll i,tmp,num,cnt=1;
while(scanf("%I64d",&m)!=EOF)
{
num=0;
for(i=2;i*i<=2*m+10;i++)
{
tmp=binary_search(i);
if(tmp!=-1)
num++;
}
printf("%I64d\n",num+1);
}
return 0;
}