2016年第七届蓝桥杯省赛-H. 四平方和

2021-12-23 · 193次阅读 · 原创 · 数据结构与算法

#题解 #蓝桥杯

原题链接

题面

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

比如：

$5 = 0^2 + 0^2 + 1^2 + 2^2$ ；

$7 = 1^2 + 1^2 + 1^2 + 2^2$ ；

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

$0 \leq a \leq b \leq c \leq d$

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

输入描述

程序输入为一个正整数 N ( $N<5 \times 10^6$ )。

输出描述

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

输入样例

输出样例

0 2 2 2

题解

枚举

由题，可以发现要求的四个数必小于等于 sqrt(n)，题目要求最小字典序的四个数，则从0开始枚举前三个数 a b c，最大为 sqrt(n)，再将 n 减去前三个的平方和，判断是否存在满足要求的第四个整数即可。

代码

#include<bits/stdc++.h>

using namespace std;

int n, m;

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

    return 0;
}

标题：	2016年第七届蓝桥杯省赛-H. 四平方和
链接：	https://www.fightingok.cn/detail/186
更新：	2022-09-18 22:46:29
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可