四平方和(二分)

一个数可以分为四个正整数的平方和(包括0)，且四个数0≤a≤b≤c≤d，对于一个正整数的所有四平方和表示方法，按字典序输出第一种表示方法的四个数字

思路：
1.枚举所有的c、d，按c^2+d^2、c、d的字典序排序，存储到结构体sum，从小到大枚举a、b，可求出每一对a、b对应其各自的的c^2+d^2=t=n-a^2+b^2，二分查找出大于等于t的最小的c^2+d^2，若t==c^2+d^2找到的值则为答案
2.从小到大枚举c、d，c<d恒成立，从小到大枚举a、b，a<b恒成立，若出现a=2，b=1的情况，则一定已经存在a=1，b=2的情形，字典序较小的会先被枚举到，因此不会漏下情形

数据范围：
0<N<5∗106

输入样例：
5

输出样例：
0 0 1 2

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

    const int N = 5000010;
    int n, m;

    struct Sum
    {
        int s, c, d;
        bool operator < (const Sum &t)
        {
            if(s != t.s) return s < t.s;
            if(c != t.c) return c < t.c;
            return d < t.d;
        }
    }sum[N];

    int main()
    {
        cin >> n;

        // n分成4个数abcd，且0 ≤ a ≤ b ≤ c ≤ d
        for(int c = 0; c*c <= n; c++) //枚举所有的c、d，记录c^2 + d^2，并按c^2+d^2, c, d按字典序排序
            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++) //枚举所有的a^2 + b^2
            for(int b = 0; a*a + b*b <= n; b++)
            {
                int l = 0, r = m - 1;
                int t = n - a*a - b*b; //t为当前a、b对应的c^2+d^2的和
                while(l < r) //二分找到大于等于n - a*a - b*b的最小的c^2+d^2的和
                {
                    int mid = l + r >> 1;
                    if(sum[mid].s >= t) r = mid;
                    else l = mid + 1;
                }
                if(sum[l].s == t) //找到的c^2+d^2的值正好为t，则找到答案
                {
                    printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                    return 0;
                }
            }

        return 0;
    }