pku2100.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 73 行

#include <stdio.h>
#include <math.h>

typedef struct 
{
	int s;
	int l;
} Ans;

Ans p[2000];

__int64 calc(int s, int e)
{
	__int64 ans, a, b;
	a = s - 1;
	b = e - 1;
	if (e == s)
	{
		return b * b;
	}
	ans = b * (b + 1) * (2 * b + 1) - a * (a + 1) * (2 * a + 1);
	ans /= 6;
	return ans;
}
int main()
{
	__int64 S, tmp;
	int n, i, l, k, up, down, mid, j;

	while (scanf("%I64d", &S) == 1)
	{
		n = ceil( pow(S * 3, 1.0 / 3));
		k = 0;
		for (i = n; i > 0; i--)
		{
			up = floor(sqrt(1.0 * S / i)) + 1;
			down = 0;
			mid = (up + down) / 2;
			while (up - down > 1)
			{
				mid = (up + down) / 2;
				tmp = calc(mid, mid + i);
				if (tmp > S)
				{
					up = mid;
				}
				else if (tmp < S)
				{
					down = mid;
				}
				else
				{
					p[k].s = mid;
					p[k].l = i;
					k++;
					break;
				}
			}
		}
		printf("%d\n", k);
		for (i = 0; i < k; i++)
		{
			printf("%d ", p[i].l);
			for (j = 0; j < p[i].l; j++)
			{
				printf("%d ", p[i].s + j);
			}
			printf("\n");
		}
	}
	return 0;
}