C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

暴力1：三重循环

$O(n^3)$ 超时

思路:

$直接暴力枚举一下a,b,c,最后d可以通过n - a * a - b * b - c * c 开根号求得，$

$然后判断一下开根号求的d1的平方是否等于d，如果等于，那么找到正确的解了,直接输出即可$

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 5e6 + 10;

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", a, b, c, d);
                    return 0;
                }
            }
    return 0;
}

$ps1：实际上，这个暴力代码在蓝桥杯官网题库测试是可以ac的，之所以在acwing里面不能ac，$
$是因为加强了测试数据，有一个超时了，其他的都可以过的。$

$ps2：实际上，在acwing里面测试的时候，暴力代码是运行效率最快的，二分和哈希表法的耗时比暴力慢很多$

$图证:$

暴力2：三重循环（优化版）

$O(n^3)$ 可以ac

#include <bits/stdc++.h>
using namespace std;

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

二分：

$O(n^2logn)$ 可以ac

思路：

$枚举一下c,d,记录一下c^2+d^2,在枚举a,b找到符合条件的，直接输出即可$

$图解：$

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 5e6 + 10;

int n, m;

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 main() {
    cin >> n;

    for (int c = 0; c * c <= n; c ++) // 枚举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,b
        for (int b = a; 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", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }

    return 0;
}

哈希表

$O(n^2)$ 超时

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int N = 5e6 + 10;

int n, m;
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 = a; a * a + b * b <= n; b ++) {
            int t = n - a * a - b * b;
            if (S.count(t)) {
                printf("%d %d %d %d", a, b, S[t].x, S[t].y);
                return 0;
            }
        }

    return 0;
}

$\small{分享：}$

$\large\color{blue}{— > C/C++输入字符串}$