蓝桥杯练习题五 - 四平方和（c++）

题目如下

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多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

以下程序实现了这一功能，请你补全空白处内容：

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int MAXN = 2500010;
struct Node
{
    int s, c, d;
    bool operator<(const Node &t) const
    {
        if (s != t.s)
            return s < t.s;
        if (c != t.c)
            return c < t.c;
        return d < t.d;
    }
} sum[MAXN];
int n, m;
int main()
{
    cin >> n;
    for (int c = 0; c * c <= n; c++)
        for (int d = c; c * c + d * d <= n; d++)
            sum[m++] = {c * c + d * d, c, d};
    sort(sum, sum + m);
    for (int a = 0; a * a <= n; a++)
    {
        for (int b = 0; a * a + b * b <= n; b++)
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r)
            {
                __________________;
                if (sum[mid].s >= t)
                    r = mid;
                else
                    l = mid + 1;
            }
 
            if (sum[l].s == t)
            {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}

提示：

二分法降低时间复杂度
用打表空间换时间

感慨：这道题难度还是有些大的，博主也是看了好一会才想到才搞懂题目中提供的部分代码是什么意思，这里提供两种解题思路供大家思考，每种解题思路都会附上详细解释，接下来走起：

解题思路一 

#include 
using namespace std;
 
typedef long long LL;
const int MAXN = 2500010;
struct Node
{
    int s, c, d;
    bool operator<(const Node &t) const
    {
        if (s != t.s)
            return s < t.s;
        if (c != t.c)
            return c < t.c;
        return d < t.d;
    }
} sum[MAXN];
int n, m;
int main()
{
    cin >> n;
    for (int c = 0; c * c <= n; c++)
        for (int d = c; c * c + d * d <= n; d++)
            sum[m++] = {c * c + d * d, c, d};
    sort(sum, sum + m);
    for (int a = 0; a * a <= n; a++)
    {
        for (int b = 0; a * a + b * b <= n; b++)
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t)
                    r = mid;
                else
                    l = mid + 1;
            }
 
            if (sum[l].s == t)
            {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}

1.struct Node

这是一个结构体内嵌比较函数。

struct node
{
    int l,r;
    bool operator <(const node &a)const{
        return r < a.r;
    }
}a[maxn];
 

这种是最经典的。
r相当于当前正在比较的值，这个函数就是r从小到大排。
存储用优先队列时则会相反，同是上面这个函数会按r从大到小排。

优先队列如下：

struct node
{
    int l,r;
    bool operator <(const node &a)const
    {
        return r>a.r;
    }
};
priority_queue q;

但是本题中我们明显不需要这么做，只做扩展用，大家看看就好，了解一下。

本题中代码如下： 

struct Node
{
    int s, c, d;
    bool operator<(const Node &t) const
    {
        if (s != t.s)
            return s < t.s;
        if (c != t.c)
            return c < t.c;
        return d < t.d;
    }
} sum[MAXN];

其实这里还什么都没做，熟悉c++的同学应该知道这是个结构体，用sum数组的形式来存储Node结构体内的一些参数。

2.枚举c，d的for循环

    cin >> n;
    for (int c = 0; c * c <= n; c++)
        for (int d = c; c * c + d * d <= n; d++)
            sum[m++] = {c * c + d * d, c, d};
    sort(sum, sum + m);

 从for循环中，我们看到首先对c，d进行了取值，取出所有满足条件的值，这个应该不难理解，接着看sum：

sum[m++] = {c * c + d * d, c, d};

其实我觉得这里有点问题，m应该初始值为0才对，博主学c++时间不久，不给初始值直接++是否存在问题，还望小伙伴们指出来，运行发现m初始值确为0，在其他语言中，根据博主多年经验，不给初始值是不行的。

这里备注下：如果将m = 0，那么第一项势必是1，而不是0，所以c++里面才有了这种操作？

但是也可以通过m = 0，在sum[m]之后，进行m++。有懂的小伙伴评论区解答下，感谢！

这段代码是将c的平方和d的平方相加作为s，然后将s，c，d存入了结构体Node中，继而存入初始值为1的sum数组中，这样就得到了所有满足条件的c和d ，还有其平方和的值s。

结构体内嵌比较函数的使用就是直接sort就可以，sort(a,a+n);首先c一定是小于等于d的，这一点，在for循环中很容易看出来，因为d = c，d++。这里sort针对s的大小进行排序从小到大。

3.接下来要对a和b进行枚举了

    for (int a = 0; a * a <= n; a++)
    {
        for (int b = 0; a * a + b * b <= n; b++)
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t)
                    r = mid;
                else
                    l = mid + 1;
            }
 
            if (sum[l].s == t)
            {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }

两个for循环不难看懂，是a和b的平方是必须要小于n的，这点没毛病，这里为了节省加快运算效率快速找到合适的a和b，采用了二分法，l=0，r=m-1。

有意思的是下面这段代码：

int mid = l + r >> 1;

博主在其他语言里真的没这么用过，只是知道是右移一位的意思，了解下，好神奇：

这是比特操作,如
12的二进制表示是00001100,12>>1将00001100右移一位，变为00000110，即6.
又如
15的二进制表示是00001111,15>>1将00001111右移一位，变为00000111，即7.
另外<<就是左移，相当于乘以2. 

这里博主用的编辑器提示>>运算符优先级低于+，所以需要将r>>1用括号括起来，同学们注意。

接下来看比较的部分：

int t = n - a * a - b * b;
int l = 0, r = m - 1;
while (l < r)
{
    int mid = l + r >> 1;
    if (sum[mid].s >= t)
        r = mid;
    else
        l = mid + 1;
}

 t是符合条件的a和b平方后被n减后留给c和d平方和的最大数。

l是初始位，r为最大为，mid为中间为，每一次if之后，r和l重新给值，范围缩小一半，二分法，不详细说了。

直到sum[l].s == t，这里解释下，sum[mid]对应的s必须是小于等于t才能继续循环下去，不过这里用了>=是不是存在一定的问题呢，如果等于的话，sum[l].s == t，这时的mid不是刚好满足条件吗？但还需要再循环一次让sum[mid].s > t，之后执行l=mid+1才能让sum[l].s == t，多些一个判断条件来判断mid我觉得更好。

满足条件后：

printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
return 0;

输出，并直接返回，此时的a，b，c，d即是符合题目要求的，按从小到大排序的合理数字。

解题思路二

#include 
#include 
#include 
#include 
#include 
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int, int> PII;
 
int main()
{
    int n;
    cin >> n;
    unordered_map<int, PII> ans;
    for(int c = 0; c * c <= n; c ++ )//枚举C和D
        for(int d = c; d * d + c * c <= n; d ++ )
        {
            int t = c * c + d * d; //存下来这两个数的平方和
            if(ans.count(t) == 0)   
                ans[t] = {c, d};
        }
        
    for(int a = 0; a * a <= n; a ++ )
        for(int b = a; b * b + a * a <= n; b ++ )
        {
            int t = n - a * a - b * b;//看A和B的平方和还和目标差多少，看看之前存的有没有这个数
            if(ans.count(t) != 0)
            {
                printf("%d %d %d %d\n", a, b, ans[t].x, ans[t].y);
                return 0;
            }
        }
    return 0;
}

这个解题思路理解起来就容易的多了：

int t = c * c + d * d; //存下来这两个数的平方和
if(ans.count(t) == 0)   
    ans[t] = {c, d};

它是采用unordered_map的方式，这是用于存储键值和映射值组合成的元素的关联容器，以c和d的平方和sum为key， 存储一个c和d的关联容器，和第一种结构中的结构体很相似。

接着是和的判断组合：

int t = n - a * a - b * b;
//看A和B的平方和还和目标差多少，看看之前存的有没有这个数
if(ans.count(t) != 0)
{
    printf("%d %d %d %d\n", a, b, ans[t].x, ans[t].y);
    return 0;
}

这里反其道而行之，不通过二分法下标去寻找值，而是根据t，也就是留给c和d平方和的最大数作为key去ans中寻找是否存在这样的sum值，这个sum值在上面介绍了，是c和d的平方和，被作为key存入了map中，只要ans.count(t) != 0，就说明存在这样的一个c和d。

总结

个人认为，第二种解题思路让人更容易理解，也更加简单直观，从效率上来说，第二种明显是要高效一点的，因为通过准确的键值去寻找符合的c和d。想出这种解题思路的人真是厉害，佩服。

看题1小时，写博客三个小时，写完之后思路更加清晰了，不知道同学们搞明白没？欢迎评论区留言讨论。