题意分析

乔治国王需要设计一个皇家陵园，陵园由多个正方形的墓群区域组成，每个区域的边长是连续的正整数，且所有区域的墓群数量（即边长的平方）互不相同。给定总墓穴数n，我们需要找出所有满足条件的陵园设计方案。每个方案由若干个连续的正整数边长组成，这些边长的平方和等于n。输出时，方案按区域数量从大到小排列。

解题思路

$1$.​问题转化​：我们需要找到所有连续的整数序列$s,s+1,s+2,…,s+l−1$，使得这些数的平方和等于n。即：

$$\sum_{i=s}^{s+l-1} i^2 = n$$

$2$.数学公式​：连续整数的平方和可以用公式表示。对于从a到b的连续整数平方和：

$$\sum_{i=a}^{b} i^2 = \frac{b(b+1)(2b+1)}{6} - \frac{(a-1)a(2a-1)}{6} $$

但直接计算这个和可能会比较复杂，我们可以采用滑动窗口的方法来高效地寻找满足条件的序列。

$3$. (1)初始化两个指针$left$和$right$，从$1$开始。

(2)维护一个当前和$sum$，表示从$left$到$right−1$的平方和。

(3)如果$sum<n$，则增加$right$，并将$right^ 2$加到$sum$中。

(4)如果$sum==n$，则找到一个有效序列$[left,right−1]$，记录下来。

(5)如果$sum>n$，则增加left，并将$left^ 2$从sum中减去。

(6)重复上述步骤直到$left$超过可能的范围。

$4$.边界条件

(1)由于n可以达到$10^{ 14}$，$right$的最大可能值约为$\sqrt{n}$​，即最多$10^ 7$左右.

(2)需要确保$right$不超过这个上限，避免无限循环。

$5$.输出排序：找到所有方案后，按区域数量$l$从大到小排序输出。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

class GraveyardDesign {
private:
	ll num;
	vector<vector<ll>> solutions;
	
	void saveSolution(ll left, ll right) {
		vector<ll> solution;
		solution.push_back(right - left + 1); // 区域数量
		for (ll i = left; i <= right; ++i) {
			solution.push_back(i); // 区域边长
		}
		solutions.push_back(solution);
	}
	
public:
	void setNum(ll n) {
		num = n;
		solutions.clear();
	}
	
	void findSolutions() {
		ll left = 1, right = 1;
		ll sum = 0;
		
		while (true) {
			// 扩展右边界直到sum >= num
			while (sum < num && right <= 1e7) {  // 1e7是足够大的上限
				sum += right * right;
				++right;
			}
			
			if (sum < num) break; // 无法再找到更大的和
			
			if (sum == num) {
				saveSolution(left, right - 1);
			}
			
			// 移动左边界
			sum -= left * left;
			++left;
		}
	}
	
	void printSolutions() {
		// 按区域数量从大到小排序
		sort(solutions.begin(), solutions.end(), 
			[](const vector<ll>& a, const vector<ll>& b) {
				return a[0] > b[0];
			});
		
		cout << solutions.size() << "\n";
		for (const auto& sol : solutions) {
			for (size_t i = 0; i < sol.size(); ++i) {
				cout << sol[i];
				if (i != sol.size() - 1) cout << " ";
			}
			cout << "\n";
		}
	}
};

int main() {
	GraveyardDesign solver;
	ll num;
	
	while (cin >> num) {
		solver.setNum(num);
		solver.findSolutions();
		solver.printSolutions();
	}
	
	return 0;
}