第七届蓝桥杯省赛（四平方和）---哈希

四平方和

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。

比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000) 
要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入： 
5 
则程序应该输出： 
0 0 1 2

再例如，输入： 
12 
则程序应该输出： 
0 2 2 2

再例如，输入： 
773535 
则程序应该输出： 
1 1 267 838

题解：

首先明白题目要我们输出的是第一个表示法，并且要按照升序排列（0要带上）。
所以最直观来看的方法便是四层for循环遍历寻找符合的答案。

不过我们可以对其进行优化，首先是使用三层for循环进行解答。因为我们的目标是四个数各自的平方相加为n，既然如此我们不妨只利用三层循环找出三个数，第四个数我们可以由n减去前面三个数各自的平方再开方得到，这样的话我们只用判断这个数是否为整数即可。
并且我们可以先创建一个哈希表来简单的判断一下什么可以符合题意什么不符合题意来删去一部分不用进行判断的元素。

需要注意的是由于我们i,j,k分别为第一层，第二层，第三层循环，因此若能出现小的数，其必会先出现，即四个数中最小的数必然是在i先出现，第二小的在j出现，其余同理，即我们直接将i,j,k,c输出即可，其本来便一定为按照从小到大排列的。并且由于我们只要出现的第一种，所以后面i,j,k大小反转的情况也不会出现。即若在1，3，4，5停止了，后面本应会出现的5，4，3，1到达不了了。因为会先出现第一种的情况。
所以j,k循环中起点可以为j = i,k = j。

代码：

#include<bits/stdc++.h>
using namespace std;
int hash[5000001] = {0};//打表
int n;
void Hash()//给表初始化
{
    for(int i=0;i*i<n;i++)
    {
        for(int j=0;j*j<n;j++)
        {
            if(i*i+j*j<=n)
            {
                hash[i*i+j*j] = 1;//此时满足小于等于n，所以是符合题意的，初始化为1
            }
        }
    }
}
int main()
{
    cin>>n;

    Hash();
    double c;
    for(int i=0;i*i<=n;i++)
    {
        for(int j=0;j*j<=n;j++)
        {//先定义两层循环，任意找出两个数
            if(hash[n-i*i-j*j]==0)
//判断n在减去他俩各自的平方后剩余的数是否可以为符合题意的数，即用到了我们前面给哈希表初始化的过程
            {
                continue;
            }
            else
            {
                for(int k=0;k*k<=n;k++)//再任意找出一个数
                {
                    c = sqrt((double)(n-k*k-i*i-j*j));//第四个数先找出来
                    if(c==(int)(c))//判断是否为整数
                    {
                        cout<<i<<" "<<j<<" "<<k<<" "<<c<<endl;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}