洛谷P1147 连续自然数和

水深无声 2022-05-30 12:07 195阅读 0赞

## 题目描述 ##

对一个给定的自然数M，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为M。

例子：1998+1999+2000+2001+2002 = 10000，所以从1998到2002的一个自然数段为M=10000的一个解。

## 输入输出格式 ##

输入格式：

包含一个整数的单独一行给出M的值（10 <= M <= 2,000,000）。

输出格式：

每行两个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

![70][]

解法一：

我用的是前缀和作的。

先求出1到M/2+1的前缀和，为什么是M/2+1，因为这之后的数字相加肯定会超过M。

然后二重循环遍历，直到找到复合a\[j\]-a\[i-1\]==M时就输出。如果a\[j\]-a\[i-1\]>M就break掉里层循环。

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    int a[2000001];
    int n;
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n;
    
    	for (int i = 1; i <= n / 2+1; i++)
    		a[i] += a[i - 1]+i;
    
    	for (int i = 0; i <= n / 2+1; i++)
    	{
    		for (int j = i + 1; j <= n / 2 + 1; j++)
    		{
    			if (a[j] - a[i - 1] == n)
    				printf("%d %d\n", i, j);
    			else if (a[j] - a[i - 1] > n) break;
    		}
    	}
    	return 0;
    }

解法二：

参考题解：[https://www.luogu.org/blog/user2981/solution-p1147][https_www.luogu.org_blog_user2981_solution-p1147]

这使用的是纯数学方法，求和公式+二次方程求根，挺厉害的!

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cmath>
    #define long long LL
    using namespace std;
    int main()
    {
        LL m;
        cin>>m;
        LL n,a1,i;
        double r;
        LL b,c,d;
        for(i=0;i<=m;i++)
        {
            a1=i;
            b=(2*a1-1);
            c=-2*m;
            d=b*b-4*c;//delta判别式
            r=-b+sqrt(d);//求根公式分号上面那一堆东西
            if(r==(int)r&&r>0)//某些时候-b会大于sqrt(d)，导致r为负，很明显这种情况不存在
            {
                n=r/2;//项数
                if(a1==a1+n-1)
                    continue;//避免只有一项的情况
                cout<<a1<<' '<<a1+n-1<<' '<<endl;    
            }
        }
        return 0;
    }

[70]: /images/20220530/8a6424ed9cb640c18a7346a5ac75f2d8.png
[https_www.luogu.org_blog_user2981_solution-p1147]: https://www.luogu.org/blog/user2981/solution-p1147