我的思路是这样的:
可以枚举数列的长度,因为长度最多是sqrt(2*m)这里解一下那个上限的方程就可以轻松算出,最多只需要计算2000次左右。
第二步:在枚举了长度l之后。可以枚举起点。因为公差为1,所以知道起点和长度就知道终点的位置。于是可以枚举起点,这里单纯枚举自然很麻烦而且复杂度很高,于是可以用二分枚举。
我的代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int start;
int end;
};
node ans[5000];
int m;
int cal(int s,int x)
{
return (2*s+x-1)*x;
}
int binary_search(int x)
{
int 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;
}
bool cmp(node a,node b)
{
return a.start<b.start;
}
int main()
{
int i,tmp,num;
while(scanf("%d",&m)!=EOF)
{
num=0;
for(i=2;i*i<=2*m+10;i++)
{
tmp=binary_search(i);
if(tmp!=-1)
{
ans[num].start=tmp;
ans[num].end=tmp+i-1;
num++;
}
}
sort(ans,ans+num,cmp);
for(i=0;i<num;i++)
printf("%d %d\n",ans[i].start,ans[i].end);
}
return 0;
}