1221. 四平方和（二分）

1221. 四平方和

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

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

比如：

5=0²+0²+1²+2²
7=1²+1²+1²+2²
对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入格式
输入一个正整数 N。

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

数据范围

0<N<5?106

输入样例：

5

输出样例：

0 0 1 2

题目分析

由于题目的数据范围，我们是不能直接进行暴力枚举
我们只能枚举两个变量，但是我们可以使用空间来置换时间，我们在枚举两个变量后，将两个变量的平方和存储下来，再次对另外两个变量进行枚举，同时与存储的两个变量的和进行比较，如果相同的话则说明是符合题目要求的答案，反之则不是答案
同时我们需要满足字典序的输出要求

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N=2500010;int n, m;struct Sum{
    int sum, c, d;bool operator< (const Sum &t) const{
    if(sum != t.sum) return sum < t.sum;if(c != t.c) return c < t.c;return d < t.d;}
}sum[N]; 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].sum >= t) r = mid;else l = mid + 1;}if(sum[l].sum == t){
    cout << a << ' ' << b << ' ' << sum[l].c << ' ' << sum[l].d << endl;return 0;}}return 0;
}