华师一附中OI组

标题: P1147 连续自然数和 [打印本页]

作者: admin 时间: 2020-3-1 16:46
标题: P1147 连续自然数和
https://www.luogu.com.cn/problem/P1147

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

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

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

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

输入输出样例
输入
10000
输出
18 142
297 328
388 412
1998 2002

作者: admin 时间: 2020-3-1 16:58
这个题很有深意，做法很多：
一、先看最基本的小学生的做法，因为L到R之间的一段的和可以等差数列求和S=(L+R)*(R-L+1)/2。
枚举L和R，判断是否可行，复杂度O(n^3)
二、前缀和优化为O(n^2)
三、用数学的方法把2*M=(L+R)*(R-L+1)分解因数，设2*M=X1*X2，(X1<X2)，则X1=(R-L+1)，X2=(L+R)，在判断是否可行分解因数朴素做法O(sqrt(n))，判断O(1)，总的在O(sqrt(n))
四、双指针法，L和R两个指针，求出L和R之间的数字和S，若S==M，输出解，若S<M，R++，若S>M，L++ 有点像队列哦，O(2*n)

作者: admin 时间: 2020-3-1 19:24
变形情况
1、不是连续，但是全为正
2、有可能有负数
3、环状
4、平面

欢迎光临华师一附中OI组 (http://hsyit.cn/)