【蓝桥杯题解】拉格朗日 ——四平方和

四平方和

• 🌟题目
• 🌟思路
• 🌟C++代码
• • 暴力做法

---

前言：
欢迎关注我的专栏专栏链接,里面是我刷过的蓝桥杯真题 ，有题目链接 + 题解。

🚀🚀🚀

🌟题目

链接

🌟思路

• 暴力做法 O(n³)：根据题意每个数都小于sqrt(n),由此枚举a,b,c 。
  

  
  

  然后d用公式求，枚举的时候a<=b<=c,符合字典序 ，找到答案就退出。
  

  
  

• 二分做法:O(n² * logn): 待补充 还没学结构体
  可以先看这个题解
  看到评论提醒我一下，不然我又忘记了🌹

🌟C++代码 暴力做法

#include  
using namespace std;
int n, a, b, c, d;
int main () {
    cin >> n;
    //开根sqrt返回类型为 double 需要类型转化为 int  
    int sqr = (int)(sqrt(n));//四个数都小于 n^(1/2)
    for (a = 0; a <= sqr; a ++) {
        for (b = a; b <= sqr; b ++) {
            for (c = b; c <= sqr; c ++) {
                d = sqrt(n - a * a - b * b - c * c);
                if (n == (d*d + a*a + b*b + c*c)) {
                    printf("%d %d %d %d\n", a, b, c, d);
                    return 0;//找到答案就退出 因为答案不唯一 有多组
                }
            }
        }
    }
}

结尾：
感谢你能看到这里，希望对你有帮助，文章如有错误还请斧正~