#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long long N, i, j, p, q;
    while(cin >> N)
    {
        int flag = 0;
        long long n = sqrt(N);
        for(i = 0; i <= n; i++)
        {
            for(j = i; j <= n; j++)
            {
                long long s = N-i*i-j*j;
                for(p = j; p < s; p++)
                {
                    for(q = p; q <= s&&q>=p; q++)
                    {
                        if(s==p*p+q*q)
                        {
                            cout << i << " " << j <<" "<< p <<" "<< q <<endl;
                            flag = 1;
                            break;
                        }
                    }
                    if(flag) break;
                }
                if(flag) break;
            }
            if(flag) break;
        }
    }
    return 0;
}

1000000里面共有1000个完全平方数~

可以建立一个平方数数组~用里面的数组合就行了~

也就是说选择其中三个数第四个数已经确定了~

如果想提高效率~

还可以建立一个a^2+b^2的状态数组~
先判断a^2+b^2是否在状态数组里面~
如果在~则再求a^2+b^2的解~

试试这个~就是感觉数组开大了一点~

#include<stdio.h>
#include<math.h>

#define N 1000000

typedef struct Node
{
    unsigned short i;
    unsigned short j;

}Node;

Node a[N+1]={0};

void Init();
void fun(int n);

void Data(int temp[],int* k,int n);

int main()
{
    int n=0;
    Init();

    while (scanf("%d",&n)!=EOF)
        fun(n);

    return 0;
}

void Init()
{
    int i=0;
    int j=0;

    int t=(int )sqrt(N);

    for (i=0;i<=t;++i)
        for (j=0;j<=t;++j)
        {
            if (i*i+j*j>N)
                break;

            if (a[i*i+j*j].i+a[i*i+j*j].j!=0)
                continue;

            a[i*i+j*j].i=i;
            a[i*i+j*j].j=j;
        }

}

void fun(int n)
{
    int m=n;
    int k=0;
    int i=0;
    int j=0;
    int flag=0;
    int temp[4]={0};

    if (n>N)
    {
        puts("超过数据指定范围!");
        return ;
    }

    if (n<0)
    {
        puts("输入数据不能小于0!");
        return ;
    }

    if (fmod(sqrt(n),1.0)==0)
    {
        printf("0 0 0 %d\n",(int)sqrt(n));
        return ;
    }

    if (a[n].i+a[n].j!=0)
    {
        printf("0 0 %d %d\n",a[n].i,a[n].j);
        return ;
    }

    while (m>=0)
    {
        int k=0;
        int s=0;

        while (m&&((a[m].i+a[m].j==0)||(a[n-m].i+a[n-m].j==0)))
            --m;

        if (flag==0&&m==0&&n!=0)
        {
            puts("不能由4个开方数组成!");
            return ;
        }

        flag=1;

        if (m==0)
            break;

        if (a[m].i!=0)
            ++s;
        if (a[m].j!=0)
            ++s;
        if (a[n-m].i!=0)
            ++s;
        if (a[n-m].j!=0)
            ++s;

        memset(temp,0,sizeof(temp));

        Data(temp,&k,a[m].i);
        Data(temp,&k,a[m].j);
        Data(temp,&k,a[n-m].i);
        Data(temp,&k,a[n-m].j);

        if (s==3)
            break;

        --m;
    }

    for (i=0;i<4;++i)
        for (j=0;j<3-i;++j)
            if (temp[j]>temp[j+1])
            {
                temp[j]^=temp[j+1];
                temp[j+1]^=temp[j];
                temp[j]^=temp[j+1];
            }

    for (i=0;i<4;++i)
        printf("%d ",temp[i]);

    puts("");
}

void Data(int temp[],int* k,int n)
{
    if (n==0)
        return ;

    temp[3-*k]=n;
    *k=*k+1;
}

[此贴子已经被作者于2017-4-7 02:15编辑过]

厉害的楼主，谢谢了，不过我还是不太懂。。。。
Node结构体是在干嘛呢？关于数组a[]的用法我还是理解不过来，可以具体讲解一下吗？谢谢大佬

厉害的楼主，谢谢了，不过我还是不太懂。。。。
Node结构体是在干嘛呢？关于数组a[]的用法我还是理解不过来，可以具体讲解一下吗？谢谢大佬

简单点i,j就是记录一个数据a[]是哪两个完全平方数相加的状态~把四个数据拆分成两组两个数据处理~如果不计初始化时间~这个方法算法空间和时间复杂度都是o(n)
~~