题目内容

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;
}
最后修改日期:2020年3月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。