本文共 1429 字，大约阅读时间需要 4 分钟。
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗106输入样例：
5输出样例：
0 0 1 2利用空间换时间的思想，因为时间限制问题因此采取枚举两轮而不是直接枚举三轮，枚举后保存两个数的平方和的结果。枚举前两个数根据剩下的平方和来寻找可能的结果，并且找字典序最小的（注：因为是按两个数的字典序来枚举的，所以已经保证了a0<=b0 ,c0<=d0，又因为这个问题必定是有解的因此如果有b0>c0的情况，则在之前枚举 a=a0,b=c0 的时候一定也能找到解，因此第一次找到的解必定是字典序排列的所求解）
代码：
#include<iostream>#include<algorithm>#include<cmath>using namespace std;const int N=2000010;int n,m;struct Node{ int s,x,y; bool operator< (const Node &t)const{ if(t.s!=s) return s<t.s; else if(t.x!=x) return x<t.x; else return y<t.y; }}record[N];int main(){ cin >> n; //排序 for(int i=0;i*i<=n;i++){ for(int j=i;i*i+j*j<=n;j++){ record[m++]={ i*i+j*j,i,j}; } } sort(record,record+m); 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; int l=0,r=m-1; while(l<r){ int mid=(l+r)/2; if(record[mid].s>=t) r=mid; else l=mid+1; } if(record[l].s==t){ printf("%d %d %d %d",a,b,record[l].x,record[l].y); return 0; } } }}转载地址：http://okbwz.baihongyu.com/