题目链接

Graveyard Design POJ - 2100

思路

$$ 尺取法 $$

时间复杂度

$$ O(N^{1/2}) $$

代码

#include <cstdio>
#include <vector>

using namespace std;

int main() {
    long long x;
    scanf("%lld", &x);// don't forget &

    int s = 1, t = 1;
    long long sum = 0;
    int n = 1e7 + 5;
    vector<int> a, b;
    while (true) {
        while (t <= n && sum < x) {
            sum += 1LL * t * t;
            t++;
        }
        if (sum < x || s > n) {
            break;
        }
        if (sum == x) {
            a.push_back(s);
            b.push_back(t);
        }
        sum -= 1LL * s * s;
        s++;
    }
    printf("%d\n", (int)a.size());
    for (int i = 0; i < (int)a.size(); i++) {
        printf("%d", b[i] - a[i]);
        for (int j = a[i]; j < b[i]; j++) {
            printf(" %d", j);
        }
        puts("");
    }

    return 0;
}