题目描述

暂留

(暴力枚举) $O(n^2)$

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2500010;
struct Sum
{
    int s, c, d;
    bool operator< (const Sum &t)const
    {
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];
int n, m;
int main()
{
    cin >> n;
    for (int c = 0; c * c <= n; c ++ ) //纯暴力的n^3分解成两个n^2
        for (int d = c; c * c + d * d <= n; d ++ )
            sum[m ++ ] = {c * c + d * d, c, d};   //把c^2+d^2加入sum数组中
    sort(sum, sum + m);   //按照c^2+d^2大小排序
    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].s >= t) r = mid;
                else l = mid + 1;                                                                                                                                               
            }
            if (sum[l].s == t){
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    return 0;
}