POJ 2100

2100.cpp

#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int, int> Pair;

int maxt;
int s;
int t;
int idx;
long long int n;
long long int sum;
Pair ans[500000];

bool cmp(const Pair &a, const Pair &b) {
    return a.second - a.first > b.second - b.first;
}

int main() {
    scanf("%lld", &n);
    maxt = (int)ceil(sqrt((double)n));
    s = 1;
    t = 0;
    sum = 0;
    while (t <= maxt) {
        while (sum <= n) {
            ++t;
            sum += (long long int)t*(long long int)t;
            if (sum == n) {
                ans[idx++] = Pair(s, t);
            }
        }

        while (sum > n) {
            sum -= (long long int)s*(long long int)s;
            s++;
            if (sum == n) {
                ans[idx++] = Pair(s, t);
            }
        }
    }

    sort(ans, ans+idx, cmp);
    printf("%d\n", idx);
    for (int j=0; j<idx; j++) {
        int s = ans[j].first;
        int t = ans[j].second;
        
        printf("%d", t-s+1);
        for (int i=s; i<=t; i++) {
            printf(" %d", i);
        }
        puts("");
    }
}