tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU 2100: Graveyard Design

概要:
ある数aが与えられるので、
a=\sum_{k=m}^n {k^2}
であらわせるものをすべて出力せよ。

解法:
基本的にはしゃくとり法でいけます。
f(x)=x(x+1)(2x+1)を用意してf(n)-f(m-1)を計算するとかやりたくなりますが、
よく考えるとx\leq 10^7くらいなのでオーバーフローします。
ここで普通に足し算引き算してやれば解けます。関数なんて用意したら寝るのが遅くなるだけです。

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> ans[10000];
int main(){
	long long a;
	scanf("%lld",&a);
	int now=0;
	int left=0;
	int right=1;
	long long sum=1;
	while((long long)right*(long long)right<=a){
		while(sum>a){
			left++;
			sum-=(long long)left*left;
		}
		if(sum==a)ans[now++]=make_pair(right-left,left+1);
		right++;
		sum+=(long long)right*right;
	}
	printf("%d\n",now);
	for(int i=0;i<now;i++){
		printf("%d",ans[i].first);
		for(int j=0;j<ans[i].first;j++)printf(" %d",ans[i].second+j);
		printf("\n");
	}
}