解题报告 P1147 连续自然数和

题目内容

P1147

大意：给定一整数 N ，求所有的区间 [l,r] (l<r) ，使得 l,r\in\mathbb{N} 且 \sum_{i=l}^ri=N

解题思路

这道题就是求连续自然数和等于 N 的所有区间，思路有两种，一种是比较好想的双指针，另一种就是直接枚举 N 的因子。最终双指针更快一些。

双指针：用两个指针 i. j 扫描，求出 [i,j] 的区间和并保持 i\not=j ，当 sum 时，说明少了，将 j 加一，当 sum > N 时，说明多了，将 i 减一，同时记得操作 sum ，如果刚好相等，输出答案并继续枚举。

#include <cstdio>

int main()
{
    int m;
    scanf("%d",&m);
    int sum=1;
    for(int i=0,j=1;i<j&&i<m/2+1;)//只需枚举到m/2即可
    {
        if(sum<m)
            sum+=++j;//小了，j加一，sum同时增加加一后的j
        else if(sum>m)
            sum-=i++;//大了，减一，sum-i然后i加一
        else if(sum==m)
            printf("%d %d\n",i,j),sum-=i++;//打印答案之后记得继续向前枚举
    }
    return 0;
}

枚举因子：由于等差数列可以看作中间项乘以项数，所以完全可以通过枚举 N 的因子判断中间项，然后筛掉不合要求的，项数是偶数时除出来的一定是 .5 结尾的，项数是奇数时一定除得尽。记得特判，具体看代码：

#include <cstdio>
#include <cmath>

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=n;i>1;i--)//i是枚举项数
    {
        if(((!(n%i) && i&1) //如果能整除且项数为奇数
          || (fabs((n/(double)i)-(n/i)-0.5)<1e-5))//或者以.5结尾并且项数为偶数
          && n/(double)i-i/2.0>0)//要求最小项不能越界
        {
            if(fabs((n/(double)i)-(n/i)-0.5)<1e-5)//偶数项
                printf("%d %d\n",n/i-i/2+1,n/i+i/2);//打印左右边界
            else
                printf("%d %d\n",n/i-i/2,n/i+i/2);//奇数项
        }
    }
    return 0;
}