POJ-2100 : Graveyard Design

問題概要

正整数n(<10^14)が与えられる。sum_{i in [l,r]} i*i == nとなる区間[l,r]を全て列挙する問題。

解法

しゃくとり法。

acceptされたコード

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

typedef long long int64;

int64 N;

int64 sq(int64 x) {
	return x * x;
}

void solve() {
	vector< pair<int,int> > ans; //(length, begin)
	for (int64 l = 1, r = 1, sum = 0; sq(l) <= N ; sum -= sq(l++)) {
		for (;sum < N;) sum += sq(r++);
		if (sum == N) {
			ans.push_back(make_pair((int)(r-l), (int)l));
		}
	}

	sort(ans.rbegin(), ans.rend());
	printf("%d\n", (int)ans.size());
	for (int i = 0; i < (int)ans.size(); ++i) {
		printf("%d ", ans[i].first);
		for (int j = 0; j < ans[i].first; ++j) {
			printf("%d%c", ans[i].second + j, j == ans[i].first - 1 ? '\n': ' ');
		}
	}
}

void init() {
	scanf("%lld", &N);
}

int main() {
	init();
	solve();

	return 0;
}