四平方定理

题目：

输入方式：

输入一个正整数 N。

输出方式：

输出4个非负整数，按从小到大排序，中间用空格分开。

代码部分：

方法一：
暴力  能过75%的数据
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n;cin>>n;
    for(int i=0;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int k=j;k<=n;k++)
            {
                int s=n-i*i-j*j-k*k;
                int d=sqrt(s);
                if(d>=k&&d<=n&&d*d==s)
                {
                    cout<<i<<" "<<j<<" "<<k<<" "<<d<<endl;
                    return 0;
                }
            }
        }
    }
}
方法二：
在方法一的基础上优化一下 能过大约92%的数据
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n;cin>>n;
    for(int i=0;i*i<=n;i++)
    {
        for(int j=i;j*j<=n;j++)
        {
            for(int k=j;k*k<=n;k++)
            {
                int s=n-i*i-j*j-k*k;
                int d=sqrt(s);
                if(d>=k&&d<=n&&d*d==s)
                {
                    cout<<i<<" "<<j<<" "<<k<<" "<<d<<endl;
                    return 0;
                }
            }
        }
    }
}
 方法三：
stl容器中的哈希表 能过75%的数据
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+10;
typedef pair<int,int> PII;
unordered_map<int,PII> q;
int main ()
{
	int n;cin>>n;
	for(int a=0;a*a<=n;a++)
	{
		for(int b=a;a*a+b*b<=n;b++)
		{
			int s=a*a+b*b;
			if(!q.count(s)) q[s]={a,b};
		}
	}
	for(int c=0;c*c<=n;c++)
	{
		for(int d=c;c*c+d<=n;d++)
		{
			int t=n-c*c-d*d;
			if(q.count(t))
			{
				cout<<c<<" "<<d<<" "<<q[t].first<<" "<<q[t].second<<endl;	
				return 0;
			}
		}
	}
	return 0;
}
方法四:
数组模拟哈希表
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int r[N];// 数组模拟
int main ()
{
    memset(r,-1,sizeof r);
    int n;cin>>n;
    for(int a=0;a*a<=n;a++)
    {
        for(int b=a;a*a+b*b<=n;b++)
        {
            int t=a*a+b*b;
            if(r[t]==-1) r[t]=a;
        }
    }
    for(int c=0;c*c<=n;c++)
    {
        for(int d=c;c*c+d*d<=n;d++)
        {
            int s=n-c*c-d*d;
            if(r[s]!=-1)
            {
                int a=r[s];
                int b=sqrt(s-a*a);
                cout<<c<<" "<<d<<" "<<a<<" "<<b<<endl;
                return 0;
            }
        }
    }
    return 0;
}
方法五
二分
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+10;
struct node{
    int s,x,y;
}e[N];
bool cmp(node a,node b)
{
    if(a.s!=b.s) return a.s<b.s;
    else if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
int main ()
{
    int n;cin>>n;
    int m=0;
    for(int c=0;c*c<=n;c++)
    {
        for(int d=c;c*c+d*d<=n;d++)
        {
            int s=c*c+d*d;
            e[m++]={s,c,d};
        }
    }
    sort(e,e+m,cmp);
    for(int a=0;a*a<=n;a++)
    {
        for(int b=a;a*a+b*b<=n;b++)
        {
            int s=n-a*a-b*b;
            int l=0,r=m-1;
            while(l<r)
            {
                int mid=(l+r)/2;
                if(e[mid].s>=s) r=mid;
                else l=mid+1;
            } 
            if(e[l].s==s)
            {
                cout<<a<<" "<<b<<" "<<e[l].x<<" "<<e[l].y<<endl;
                return 0;
            }
        }
    }
    return 0;
}

• 亲亲们可以给个赞赞吗