题意

image-20230320174956771

输入格式

输入一个正整数 N。

输出格式

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

数据范围

0<N<5∗10^6

样例1

input
5
output
0 0 1 2

思路

这题三重循环暴力能过，反而比正常做法还快找到解。。。不愧是暴力杯。

(～￣▽￣)～
不管它水不水，我们先来看看两种正常点的做法：哈希和二分。

好吧最后我们想想为什么这道题暴力更快：我们三重枚举理论上时间复杂度是O(N^3)（最坏），但问题是这道题它的答案都很小，所以我们早早就能找到解。这题不典型。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 二分做法
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2500005;

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 n, m;

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].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;
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 哈希做法
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
const int N = 2500005;

int n;
unordered_map<int, PII> S;

int main() {
    cin >> n;
    for (int c = 0; c*c <= n; c++)
        for (int d = c; c*c+d*d <= n; d++) {
            int t = c*c+d*d;
            if (S.count(t) == 0) S[t] = {c, d};
        }

    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;
            if (S.count(t)) {
                printf("%d %d %d %d\n", a, b, S[t].fi, S[t].se);
                return 0;
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 暴力做法
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2500010;

int n;
int main() {
    cin >> n;
    for (int a = 0; a*a <= n; a++)
        for (int b = a; a*a+b*b <= n; b++)
            for (int c = b; a*a+b*b+c*c <= n; c++) {
                int t = n-a*a-b*b-c*c;
                int d = sqrt(t);
                if (d*d == t) {
                    printf("%d %d %d %d\n", a, b, c, d);
                    return 0;
                }
            }
}