欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

第七届蓝桥杯 四平方和

程序员文章站 2022-04-16 09:26:34
转载请注明出处:http://www.cnblogs.com/zhishoumuguinian/p/8372337.html 四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去,就正好可以表示为4个数的平方和。比如:5 = 0^2 + 0^2 + 1^2 ......

转载请注明出处:http://www.cnblogs.com/zhishoumuguinian/p/8372337.html

四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去,就正好可以表示为4个数的平方和。比如:5 = 0^2 + 0^2 + 1^2 + 2^2    7 = 1^2 + 1^2 + 1^2 + 2^2   (^符号表示乘方的意思)对于一个给定的正整数,可存在多种平方和的表示法。要求你对4个数排序:0 <= a <= b <= c <= d。并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。程序输入为一个正整数N (N<5000000),要求输出4个非负整数,按从小到大排序,中间用空格分开

例如,输入:
5
则程序应该输出:
0 0 1 2

再例如,输入:
12
则程序应该输出:
0 2 2 2

再例如,输入:
773535
则程序应该输出:
1 1 267 838

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

 

思路:四个数的平放,第一想法是四层循环,但是最后一层循可以省略。每层循环到sqrt(5000000)+1即可,可以先输出一下,sqrt(5000000)+1值为2237。大题思路就是这样,接下来粘上代码。

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 
 6 int main()
 7 {
 8     int  n;
 9      cin>>n;
10     //n=5000000;
11     for(int a=0; a<=2237; a++)
12     {
13         for(int b=0; b<=2237; b++)
14         {
15             for(int c=0; c<=2237; c++)
16             {
17                 int dj=n-a*a-b*b-c*c;
18                 int d=sqrt(dj);
19                 if(dj==d*d)//如果dj等于d的平方,第四位数是一个整数的平方,这个整数d就是第四位数
20                 {
21                 cout<<a<<" "<<b<<" "<<c<<" "<<d;
22                 return 0;
23                 }
24             }
25         }
26     }
27 }

题目限制时间是3秒

计算的5000000,DEV-C++执行时间           CODEBLOCKS执行时间

第七届蓝桥杯   四平方和                   第七届蓝桥杯   四平方和

如果本文对你有帮助,请给个