题目大意,给定一个整数,要你找出他的平方和组合
太简单了。。。。不过一开始我储存平方和想降低时间,后来发现会超内存,直接用时间换空间了,游标卡尺法
#include <iostream>
#include <functional>
#include <algorithm>
#define MAX_N 10000001 using namespace std;
typedef long long LL_INT; static int store[MAX_N][];//只储存开始和结尾 void Inivilize(void); int main(void)
{
LL_INT n, sum, tmp;
int s, t, num; while (~scanf("%lld", &n))
{
sum = num = ; s = t = ;
while ()
{
while ((tmp = (LL_INT)t*(LL_INT)t) <= n && sum < n)
{
sum += tmp;
t++;
}
if (sum == n)
{
store[num][] = s; store[num][] = t;
num++;
}
if (sum < n)
break;
sum -= (LL_INT)s*(LL_INT)s; s++;
}
printf("%d\n", num);
for (int i = ; i < num; i++)
{
printf("%d ", store[i][] - store[i][]);
for (int j = store[i][]; j < store[i][]; j++)
printf("%d ", j);
printf("\n");
}
}
return EXIT_SUCCESS;
}