普及-每日一题洛谷P1147
题目描述
对一个给定的正整数 \(M\)，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 \(M\)。
例子：\(1998+1999+2000+2001+2002 = 10000\)，所以从 \(1998\) 到 \(2002\) 的一个自然数段为 \(M=10000\) 的一个解。
输入格式
包含一个整数的单独一行给出 \(M\) 的值（\(10 \le M \le 2,000,000\)）。
输出格式
每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。
样例输入
10000
样例输出
18 142
297 328
388 412
1998 2002
可以采取枚举、前缀和、二分、双指针等方法
枚举+二分解出区间跨度：
思路大致如下：
-
首先处理数据范围，减少复杂度：
因为（\(10 \le M \le 2,000,000）\)，并且每一段至少有两个数，所以能保证取到 \(M=2,000,000\) 的最小区间为\([(1,000,000),(1,000,001)]\)
-
意思就是说我们只需要从 \(0\) 遍历到 \(M/2\)，对每次遍历都做一次二分搜索，没有搜索到匹配的区间跨度则退出继续遍历
-
当某一次遍历找到了匹配的区间跨度使得区间和为 \(M\) 时，输出当前遍历的左区间和二分找到的右区间
-
直到遍历结束，退出程序
具体实现如下：
find函数，寻找匹配的区间跨度：
int find(int start) {
int l = 1, r = n;
while (l<r)
{
long long mid = l + r >> 1;//long long 防止求和数据溢出
if ((start + mid + start) * (mid + 1) / 2 == n)//等差数列求和公式，二分结果可能过大
return mid;
else if ((start + mid + start) * (mid + 1) / 2 > n)
r = mid;
else
l = mid + 1;
}
return 0;//未找到匹配的区间跨度返回0
}
从 \(1\) 开始遍历到 \(M/2\):
for (int i = 1; i <= m / 2; i++) {
if (find(i) == 0) continue;//未找到匹配的区间跨度则继续遍历i
else printf("%d %d\n", i, i + find(i));//输出匹配的区间跨度
}
完整代码：
int m;
int find(int start) {
int l = 1, r = m;
while (l<r)
{
long long mid = l + r >> 1;
if ((start + mid + start) * (mid + 1) / 2 == m)
return mid;
else if ((start + mid + start) * (mid + 1) / 2 > m)
r = mid;
else
l = mid + 1;
}
return 0;
}
int main()
{
scanf("%d", &m);
for (int i = 1; i <= m / 2; i++) {
if (find(i) == 0) continue;
else printf("%d %d\n", i, i + find(i));
}
return 0;
}
枚举+前缀和找到区间：
思路如下：
- 存储前缀和到数组中，同理只需要存到第 \(1,000,000\) 项
- 遍历右区间，在存在右区间的前提下，往回检索左区间，存在匹配的左右区间，直接输出
- 因为每次遍历左区间时，区间和总是随左区间减小而增大的，如果遍历到的左区间使区间和大于 \(M\)，则直接退出
- 若遍历完左区间，未能找到匹配值，则继续遍历右区间
记录前缀和：
for (int i = 1; i <= 1000000; i++)
sum[i] += sum[i - 1] + i;
遍历右左区间：
for (int i = 1; i <= m / 2 + 1; i++) {//先遍历右区间
for (int j = i; j >= 1; j--) {//往回检索左区间
if (sum[i] - sum[j - 1] > m) break;//区间和大于M直接退出
if (sum[i] - sum[j - 1] == m && j != i) printf("%d %d\n", j, i);
}
}
完整代码：
int m,sum[1000010];
int main()
{
scanf("%d", &m);
for (int i = 1; i <= 1000000; i++)
sum[i] += sum[i - 1] + i;
for (int i = 1; i <= m / 2 + 1; i++) {
for (int j = i; j >= 1; j--) {
if (sum[i] - sum[j - 1] > m) break;
if (sum[i] - sum[j - 1] == m && j != i) printf("%d %d\n", j, i);
}
}
return 0;
}