四平方和

 Sapphire

2022/3/29

解题思路:

非常遗憾的是，我只会暴力解法，但暴力解法可以从4次遍历减少到3次遍历，这样可以避免时间超限。

注意事项:
1.这里减少遍历的方法是，因为四个元素的平方和始终等于这个元素，那我们就用N减去令三个元素的平方，再开根，如果这个数的平方确确实实和其他三个数的平方和为N，那么就检索到了(有点类似于哥德巴赫猜想)。

2.比如N是5，那么(0,0,0,根号5)的情况呢？这个嘛，很好解释，a、b、c、q都定义的整形啊，根号5可不是整数，这种情况排除。

3.a=0;a<sqrt(n)来减小复杂度。

参考代码:

#include<stdio.h>
#include<math.h>
int main()
{
    int N;
    scanf("%d",&N);
    if(N<5000000)
    {
        int a,b,c,d;
        for(a=0;a<=sqrt(N);a++)
        {
            for(b=0;b<=sqrt(N);b++)
            {
                for(c=0;c<=sqrt(N);c++)
                {
                    int q=(int)sqrt(N-a*a-b*b-c*c);
                    if(pow(q,2)+pow(a,2)+pow(b,2)+pow(c,2)==N)
                    {
                        printf("%d %d %d %d\n",a,b,c,q);
                    }
                }
            }
        }
    }
    outside:
    return 0;
}