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; }