尺取

一开始迷之wa… 先找出素数下标的上界就可以A… 然后纠结了２０分钟．．． 然后发现是预处理的素数少了一个素数．． 我预处理是处理到＜１０００５的素数．．． 最大数１００００,而超过１００００的第一个素数是１０００７ 这样判断终止条件就会死循环… sad

不多说，直接代码。 1/************************************************************************* 2 > File Name: code/poj/2100.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年09月25日 星期五 00时42分49秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#include<cctype> 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define ms(a,x) memset(a,x,sizeof(a)) 25#define lr dying111qqz 26using namespace std; 27#define For(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef double DB; 30const int inf = 0x3f3f3f3f; 31LL n; 32LL maxn; 33vector<LL>ans; 34 35 36void solve() 37{ 38 LL head = 1,tail = 1; 39 LL sum = 0 ; 40 41 while (tail<=maxn) 42 { 43 sum = sum + tail*tail; 44 45 if (sum>=n) 46 { 47 while (sum>n)//主要是while，因为可能要减掉多个才能小于n 48 { 49 sum -= head*head; 50 head++; 51 } 52 if (sum==n) 53 {//因为要先输出答案个数...所以必须存起来延迟输出... 54 ans.push_back(head); 55 ans.push_back(tail); 56 } 57 } 58 tail++; 59 } 60 LL sz = ans.size(); 61 printf("%lld\n",sz/2); 62 for (LL i = 0 ; i<ans.size() ; i = i +2) 63 { 64 printf("%lld",ans[i+1]-ans[i]+1); 65 for ( LL j = ans[i] ; j <=ans[i+1] ; j++) printf(" %lld",j); 66 printf("\n"); 67 } 68 69} 70int main() 71{ 72 #ifndef ONLINE_JUDGE 73 freopen("in.txt","r",stdin); 74 #endif 75 scanf("%lld",&n); 76 maxn = ceil(sqrt(n)); 77 solve(); 78 79 #ifndef ONLINE_JUDGE 80 fclose(stdin); 81 #endif 82 return 0; 83}