瓜老板的平方数

题解：

如果询问的数本身就是平方数，直接输出 $1$ 。

否则：

1、如果该数是奇数，设该数为 $o d d = 2 x + 1$ ，

一定有 $o d d = (x + 1)^{2} - x^{2}$

2、如果该数是偶数，设该数为 $e v e n$ ，那么它起码用 $3$ 个平方数就可以表示，即先让 $e v e n$ 减1,变成奇数的情况，然后就有：

$e v e n = 1^{2} + o d d$ 且 $o d d = (x + 1)^{2} - x^{2}$

$e v e n = 1^{2} + (x + 1)^{2} - x^{2}$

至于是否可以使用两个平方数表示出来，可以打个表，提前预处理出来所有可以仅用两个平方数表示出来的数。

偶数预处理：

首先 $(x + 2)^{2} - x^{2} = 4 x + 4 = 4 (x + 1)$ ，其中 $x\in[1,+\infty]$

所以有，所有的4的倍数都可以用2个平方数以相减的形式表示出来。

如果x不能被4整除，也就是x=2*odd，（odd是奇数）

由上面可以知道这种x只可能以2个平方数相加的形式表示出来，所以只需要预处理所有 $x = a^{2} + b^{2}$ 的这种形式，a和b一定都是在1000以内的的。

时间复杂度O(n)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int cnt, arr[N];
int ans[N];

int main()
{
	//求出所有的平方数，1e6以内有1000个
	for(int i = 1; ; i ++)
	{
		int t = i * i;
		//将t存入数组
		if(t > 1000000) break;
		arr[cnt ++] = t;
		ans[t] = 1; //标记平方数的ans=1
	}

	for(int i = 0; i < cnt; i ++)
		for(int j = 0; j < cnt; j ++)
        {
            int t = arr[i] + arr[j]; //只需要预处理相加的，相减的不需处理
			//询问的数是[1,1e6]范围内的正整数
            if(0 < t && t <= 1000000 && !ans[t])    ans[t] = 2;
        }


	int q; scanf("%d", &q);
	while (q --)
	{
		int x;
		scanf("%d", &x);
		
		if(ans[x])  printf("%d\n", ans[x]); //之前标记过
		else if((x & 1) || x % 4 == 0)  printf("2\n"); //奇数或者是4的倍数的偶数
		else    printf("3\n");
	}

	return 0;
}