$Date：2022-10-06$

$Event$ $is$ $not$ $the$ $size$ $of$ $the$ $power,$ $and$ $can$ $insist$ $on$ $how$ $long!$

🍿1. 四平方和🍿

🥗题目🥗

四平方和定理，又称拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和（如果把0包括进去，刚好表示为4个正整数的平方和），对于一个给定的正整数，可能存在多种平方和的表示法，要求对四个数进行升序排序(0 <= a <= b <= c <= d)，并对所有的可能表示法按a,b,c,d为联合主键升序排序，最后输出第一个表示法

如 数字5 有四种表示法
1. 5 = 0^2 + 0^2 + 1^2 + 2^2
2. 5 = 0^2 + 1^2 + 0^2 + 2^2
3. 5 = 0^2 + 2^2 + 0^2 + 1^2
4. 5 = 1^2 + 2^2 + 0^2 + 0^2
以上四种排序法中第一种已经按升序排序完成，所以输出结果为第一组表示法

🥗思路🥗

题目很好理解，看主要关键点，对所有的可能表示法按a,b,c,d为联合主键升序排序，最后输出第一个表示法，这里有两个关键点：1. 结果必须是升序排序的；2. 最终结果是所有可能结果中联合主键排序最小的。共同点都是升序排序，那么只要一开始就保证计算过程是按升序排序进行的，得到的第一个结果就是符合题目要求的，按照这个理解得到以下思路

1. 因为(0 <= a <= b <= c <= d)，所以可以先求最大的位，这里先求C & D
   • 轮询方式：c <= d，所以大循环为c，小循环为d，循环的终止条件都是两数平方和相加不大于给定的数n
   • 结果存储：因为要同时保存c和d两个数字，而且c和d的组合有很多种，所以常规的数组什么的不太好进行后面的取值操作，这种情况字典就比较适配了，这里用STL中提供的unordered_map进行存储（因为map可以存储任意类型的数据，这里可以设置存储类型为<int, pair<int,int>>，前者为c和d的平方和结果，后者为c和d两者本身的值
   • 结果判断：如果当前c^2 + d^2 <= n，并且之前没有记录过，则保存下这组数字
   • unordered_map & map的区别：前者内部实现了哈希表，查找速度较快；后者内部实现了红黑树，具有自动排序的功能，这里主要用到查找，所以使用前者比较好

unordered_map<int, pair<int, int>> res;
for (int c = 0; c^2 <= n; c++)
{
    for (int d = c; c^2 + d^2 <= n; d++)
    {
        int tmp = c^2 + d^2;
        if (0 == res.count(tmp))
        {
            res[tmp] = {c, d};
        }
    }
}

2. 前面已经取得了c和d的所有可能组合结果，这里就只需要求a和b的所有可能结果即可，方法还是和上面一样，不同的是
   • 结果判断：经过前面的步骤，n、c、d三个值已经固定了，那么剩余变量a和b，只需要判断n - a^2 - b^2 ?= c^2 + d^2即可，也就是判断字典中是否存在n - a^2 - b^2值的组合

for (int a = 0; a^2 <= n; a++)
{
    for (int b = a; a^2 + b^2 <= n; b++)
    {
        int tmp = n - (a^2 + b^2);
        if (0 != res.count(tmp))
        {
            //输出结果a, b, c, d
        }
    }
}

🥗代码🥗

void LQ_Base::Pikashu_SumOf4Square(int i_uNum)
{
    // 枚举C & D，并存放于哈希表中
    unordered_map<int, pair<int, int>> res;
    for (int c = 0; (c * c) <= i_uNum; c++)
    {
        for (int d = c; (d * d + c * c) <= i_uNum; d++)
        {
            int tmp = d * d + c * c;
            if (0 == res.count(tmp))
            {
                res[tmp] = {c, d};
            }
        }
    }

    // 枚举 A & B
    for(int a = 0; (a * a) <= i_uNum; a++)
    {
        for (int b = a; (b * b + a * a) <= i_uNum; b++)
        {
            int tmp = i_uNum - (b * b + a * a);
            if (0 != res.count(tmp))
            {
                cout << i_uNum << " = [" << a << "]^2 + [" << b << "]^2 + [" << res[tmp].first << "]^2 + [" << res[tmp].second << "]^2" << endl;
                return;
            }
        }
    }
    cout << "Can't find " << i_uNum << "'s sum of four square." << endl;
}

🥗总结🥗

以终为始，从最终结果反推解题步骤。既然要求都是升序排列，那么按升序轮询求出的后两个正整数，再按升序轮询求出前两个正整数，那么求出的第一组a^2 + b^2 + c^ + d^2 = n的结果就一定是题目所求的结果