山东大学考研机试题——整数序列

题目描述

传送门——AcWing 3717. 整数序列 - AcWing

很多整数可以由一段连续的正整数序列（至少两个数）相加而成，比如 25=3+4+5+6+7=12+1325=3+4+5+6+7=12+13。

输入一个整数 N，输出 N 的全部正整数序列，如果没有则输出 NONE。

输入格式

一个整数 N。

输出格式

• 每行输出一个满足条件的整数序列。

• 序列内部元素从小到大排序。

• 优先输出首项更小的序列。

数据范围

2 ≤ N ≤ 107

输入样例：

25

输出样例：

3 4 5 6 7
12 13

思路及代码

二分查找

从 1 ~ n / 2 遍历 i，通过二分查找以 i 开头时的答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7+7;
int n;
int main(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);cin>>n;LL k = n / 2;bool tag = false;for(LL i=1;i<=k;i++){// high = k + 1作为最大值是因为当最大值大于 n/2时，由于要求是一组连续的数，所以此时的序列至多有2个数LL low = i, high = k + 1;while(low < high){LL mid = low + high + 1 >> 1;if((mid - i + 1)*(i + mid) <= 2*n){low = mid;}else{high = mid -1;}}if((low - i + 1)*(i + low) == 2*n){tag = true;for(int j=i;j<=low;j++){cout<<j<<" ";}cout<<"\n";}}if(tag == false){cout<<"NONE";}return 0;
}

数学公式

该题本质考察的是一组连续数的和，则令这组连续数的开头是a，共k个数，那么这组数的和通过求和公式可得为 (a + a + k - 1) * k / 2。而我们需要求得是 a 和 k，当这两个未知数确定后，一组数便确定了。

因此考虑， (a + a + k - 1) * k / 2 = n，即 (2a + k - 1) * k = 2n，可知，由 a 和 k 组成的 y = (2a + k - 1) 和 x = k 两个公式是 2n 的因子。既然如此，我们可以去求 2n 的因子，考察满足条件的两个因子 x和y，由 x和y 可得到 a 和 k。

#include<bits/stdc++.h>
using namespace std;
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n;cin >> n;n *= 2;int cnt = 0;// 题目要求优先输出首项更小的序列，即 (2a + k - 1) * k 中的 a 更小。由 (2a + k - 1) * k = 2n 可知 k 越大 a越小，即因子 x 越大，a越小，所以这里 x 从大到小遍历 for (int x = sqrt(n); x > 1; x--) {if (n % x == 0) {int y = n / x;int t = y - (x - 1);// t = 2a，因此 t 必须是偶数if (t % 2 == 0) {cnt++;int a = t / 2;for (int i = a; i < a + x; i++) {cout << i << " ";}cout << "\n";}}}if (cnt == 0) {cout << "NONE";}return 0;
}