P1147 连续自然数和(枚举，数学/二分)

本文主要是介绍P1147 连续自然数和(枚举，数学/二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.luogu.org/problemnew/show/P1147
题目描述
对一个给定的自然数M，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为M。

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

输入输出格式
输入格式：
包含一个整数的单独一行给出M的值（10≤M≤2,000,000）。

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

输入输出样例
输入样例#1：

输出样例#1：

/*
way1:数据不大，可以直接考虑枚举+二分
way2:更快的肯定就是数学推导了
*/
way1(O(nlogn))：

#include <iostream>
using namespace std;
typedef long long LL;
int main()
{LL m;cin>>m;for(int i = 0; i < m; i++){LL s = i,e  = -1;LL low = s+1,high = m-1,mid;while(low <= high){mid = (low + high) / 2;LL temp = (s + mid) * (mid - s + 1);//这里int不够if(temp < 2 * m){low = mid + 1;}else if(temp > 2 * m){high = mid - 1;}else{e = mid;break;}}if(e != -1){cout<<s<<" "<<e<<endl;}}return 0;
}

way2 (O(n)）:
数学推导：
根据等差数列求和：

sum = (s+e) * (e-s+1) / 2
(s+e) *（e-s+1） = 2 * sum
设 s + e = x1,e-s+1 = x2;解上述方程组：e = (x1+x2-1)/2, s = (x1-x2+1)/2;再由第二个表达式：x1 * x2 = 2*sum可知2*sum一定为偶数，那么x1,x2可能有两种情况：1.两个都是偶数2.一奇一偶根据 e = (x1+x2-1)/2, s = (x1-x2+1)/2; 并且要是自然数解，那么x1+x2-1与x1-x2+1必定要为偶数，so可以排除第一种情况，所以x1,x2必定一奇一偶根据x1,x2必定一奇一偶，枚举其中一个,根据x1 * x2 = 2*sum得出另一个，再根据 e = (x1+x2-1)/2, s = (x1-x2+1)/2就可以求出结果了。比如枚举x2，根据x1 * x2 = 2*sum,确定x2的上限：up <= sqrt(2*sum),后续看代码~

#include <iostream>
#include <math.h>
using namespace std;
typedef long long LL;//其实int就够
int main()
{LL m;cin>>m;LL s,e,x1,x2;LL up= sqrt(2*m);for(int i = up; i > 1; i--)//逆序枚举x2，因为影响s,e起主导作用的是x1{x2 = i;x1 = 2 * m / x2;if(((x2&1) && !(x1&1)) || (!(x2&1) && (x1&1))){if(x1 * x2 == 2*m){s = (x1 - x2 + 1) >> 1;e = (x1 + x2 - 1) >> 1;cout<<s<<" "<<e<<endl;}}}return 0;
}