四平方和

题目描述

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5=0²+0²+1²+2²
7=1²+1²+1²+2²;
对于一个给定的正整数，可能存在多种平方和的表示法。

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

输入描述

程序输入为一个正整数 N(N<5×10⁶)。

输出描述

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

输入输出样例

示例

输入

12

输出

0 2 2 2

解题思路

穷举法
对于给定的正整数 N，我们可以使用穷举法来找到所有可能的表示法。穷举法的思路是，我们逐个检查所有可能的 a、b、c 和 d 值，其中 a、b、c、d 都是非负整数，并且满足 a≤b≤c≤d。
优化穷举范围
为了提高效率，我们可以对 a、b、c 的取值范围进行优化。由于 a、b、c、d 都是非负整数，并且 a≤b≤c≤d，所以 a 的最大值可以取到 N 的平方根，因为 a 的平方不可能大于 N。同理，b 的取值范围可以从 a 开始，最大值可以取到 (N - a²) 的平方根。c 的取值范围可以从 b 开始，最大值可以取到 (N - a² - b²) 的平方根。
计算 d 的值
在确定了 a、b、c 的值之后，我们可以计算 d 的值。d 的值是 (N - a² - b²- c²) 的平方根，并且 d 必须是一个整数。
检查是否满足条件
如果 a² + b² + c² + d² 等于 N，那么我们就找到了一个满足条件的表示法。由于我们按照从小到大的顺序进行穷举，所以找到的第一个表示法就是最小的表示法。
输出结果
最后，我们将找到的四个数按照从小到大的顺序输出，中间用空格分隔。
复杂度分析
这个算法的时间复杂度是 O (N^3/2)，因为我们使用了三层嵌套循环，每层循环的次数最多是 N 的平方根。这个算法在 N 的值不是很大时是可行的，但是对于非常大的 N，这个算法可能会非常慢。

代码实现

Python 实现

def find_four_squares(n):
    # 遍历所有可能的 a 值，从 0 到 sqrt(n)
    for a in range(int(n**0.5) + 1):
        # 遍历所有可能的 b 值，从 a 到 sqrt(n - a^2)
        for b in range(a, int((n - a*a)**0.5) + 1):
            # 遍历所有可能的 c 值，从 b 到 sqrt(n - a^2 - b^2)
            for c in range(b, int((n - a*a - b*b)**0.5) + 1):
                # 计算 d 的平方值
                d_squared = n - a*a - b*b - c*c
                # 检查 d_squared 是否为非负数
                if d_squared >= 0:
                    # 计算 d 的值
                    d = int(d_squared**0.5)
                    # 检查 d 是否为整数
                    if d * d == d_squared:
                        # 返回结果，确保 a <= b <= c <= d
                        return f"{a} {b} {c} {d}"
    # 如果没有找到，则返回报错信息
    return "No solution found"

# 输入一个正整数n
number = int(input())

# 获取结果并输出
result = find_four_squares(number)
print(result)

JAVA实现

import java.util.Scanner;

public class FourSquares {
    public static String findFourSquares(int n) {
        // 遍历所有可能的a值，从0到sqrt(n)
        for (int a = 0; a <= Math.sqrt(n); a++) {
            // 遍历所有可能的b值，从a到sqrt(n - a^2)
            for (int b = a; b <= Math.sqrt(n - a * a); b++) {
                // 遍历所有可能的c值，从b到sqrt(n - a^2 - b^2)
                for (int c = b; c <= Math.sqrt(n - a * a - b * b); c++) {
                    // 计算d的平方值
                    int dSquared = n - a * a - b * b - c * c;
                    // 检查d_squared是否为非负数
                    if (dSquared >= 0) {
                        // 计算d的值
                        int d = (int) Math.sqrt(dSquared);
                        // 检查d是否为整数
                        if (d * d == dSquared) {
                            // 返回结果，确保a <= b <= c <= d
                            return a + " " + b + " " + c + " " + d;
                        }
                    }
                }
            }
        }
        // 如果没有找到，则返回报错信息
        return "No solution found";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入一个正整数n
        int number = scanner.nextInt();
        // 获取结果并输出
        String result = findFourSquares(number);
        System.out.println(result);
        scanner.close();
    }
}

C++实现

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

string findFourSquares(int n) {
    // 遍历所有可能的a值，从0到sqrt(n)
    for (int a = 0; a <= sqrt(n); a++) {
        // 遍历所有可能的b值，从a到sqrt(n - a^2)
        for (int b = a; b <= sqrt(n - a * a); b++) {
            // 遍历所有可能的c值，从b到sqrt(n - a^2 - b^2)
            for (int c = b; c <= sqrt(n - a * a - b * b); c++) {
                // 计算d的平方值
                int dSquared = n - a * a - b * b - c * c;
                // 检查d_squared是否为非负数
                if (dSquared >= 0) {
                    // 计算d的值
                    int d = (int)sqrt(dSquared);
                    // 检查d是否为整数
                    if (d * d == dSquared) {
                        // 返回结果，确保a <= b <= c <= d
                        return to_string(a) + " " + to_string(b) + " " + to_string(c) + " " + to_string(d);
                    }
                }
            }
        }
    }
    // 如果没有找到，则返回报错信息
    return "No solution found";
}

int main() {
    int number;
    cin >> number;
    // 获取结果并输出
    string result = findFourSquares(number);
    cout << result << endl;
    return 0;
}

C实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 函数用于查找四个平方数之和等于给定数n的四个整数
char* findFourSquares(int n) {
    static char result[50];  // 用于存储最终结果字符串，足够长以容纳结果和提示信息

    for (int a = 0; a <= (int)sqrt(n); a++) {
        for (int b = a; b <= (int)sqrt(n - a * a); b++) {
            for (int c = b; c <= (int)sqrt(n - a * a - b * b); c++) {
                int dSquared = n - a * a - b * b - c * c;
                if (dSquared >= 0) {
                    int d = (int)sqrt(dSquared);
                    if (d * d == dSquared) {
                        // 格式化拼接结果字符串
                        sprintf(result, "%d %d %d %d", a, b, c, d);
                        return result;
                    }
                }
            }
        }
    }
    // 如果没找到，将提示信息存入结果字符串
    sprintf(result, "No solution found");
    return result;
}

int main() {
    int number;
    scanf("%d", &number);

    char* output = findFourSquares(number);
    printf("%s\n", output);

    return 0;
}

运行结果

>>> 12
0 2 2 2