3136252_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

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

using namespace std;

struct node
{
	int l, n;
};

vector <node> ans;

int main()
{
	int flag;
	__int64 i, l, sum, tmp, tt;
	__int64 min, max, mid, s;

	scanf("%I64d",&sum);
	tt = (__int64)sqrt((double)sum);
	tmp = (__int64)pow((double)sum,(1.0/3.0));
	tmp *= 10;
	for(l = tmp; l > 0; l--)
	{
		min = 0;max = tt;
		flag = 0;
		while(min <= max)
		{
			mid = (min+max)>>1;
			if(mid < l)
			{
				min = mid+1;
				continue;
			}
			s = 2*mid*mid*mid+3*mid*mid+mid;
			s -= 2*(mid-l)*(mid-l)*(mid-l)+3*(mid-l)*(mid-l)+(mid-l);
			s /= 6;
			if(s==sum)
			{
				flag = 1;
				min = mid;
				break;
			}
			else
			{
				if(s < sum)
					min = mid+1;
				else
					max = mid-1;
			}
		}
		if(flag==1)
		{
			node t;
			t.l = l;t.n = min;
			ans.push_back(t);
		}
	}
	printf("%d\n",ans.size());
	for(int it = 0; it < ans.size(); it++)
	{
		printf("%d",ans[it].l);
		for(i = ans[it].n-ans[it].l+1; i <= ans[it].n; i++)
		{
			printf(" %I64d",i);
		}
		printf("\n");
	}
	return 0;
}