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

题目描述

传送门——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
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<" ";
			}
			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
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;
}