PKU 2100: Graveyard Design
概要:
ある数aが与えられるので、
であらわせるものをすべて出力せよ。
解法:
基本的にはしゃくとり法でいけます。
を用意してを計算するとかやりたくなりますが、
よく考えるとくらいなのでオーバーフローします。
ここで普通に足し算引き算してやれば解けます。関数なんて用意したら寝るのが遅くなるだけです。
#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"); } }