18 条题解

  • 29
    @ 2023-3-25 15:37:20

    P1011 四平方和

    题目描述

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

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

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

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

    要求你对 4 个数排序使得 0≤a≤b≤c≤d。

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

    思路

    判断谁都会：

    for(int a = 0;a * a <= n;a++)
    {
        for(int b = 0;b * b <= n;b++)
        {
            for(int c = 0;c * c <= n;c++)
            {
                for(int d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                    }
                }
            }
        }
    }

    但：

    image

    优化！

    主要是优化一下a，b，c，d的上限。

    a有4个数，并且递增，那上限是n / 4;

    b有3个数，并且递增，那上限是n / 3;

    c有2个数，并且递增，那上限是n / 2;

    d有1个数，并且递增，那上限是n / 1,n;

    for(int a = 0;a * a <= n / 4;a++)
    {
        for(int b = 0;b * b <= n / 3;b++)
        {
            for(int c = 0;c * c <= n / 2;c++)
            {
                for(int d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                    }
                }
            }
        }
    }

    image

    ......

    为啥？return 0！

    已经找到了，却还要枚举完？

    for(int a = 0;a * a <= n / 4;a++)
    {
        for(int b = 0;b * b <= n / 3;b++)
        {
            for(int c = 0;c * c <= n / 2;c++)
            {
                for(int d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }

    image

    一番核对后发现data没问题，时间罗。

    一番检查

    long long！！！！！！！！！！！！！！！！！！！！！！！！！

    参考代码：

    #include <iostream>//hetao3097453
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for(long long a = 0;a * a <= n / 4;a++)
    {
        for(long long b = 0;b * b <= n / 3;b++)
        {
            for(long long c = 0;c * c <= n / 2;c++)
            {
                for(long long d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

    hetao3097453(Bilililil @ 一钩出站)

    2023年3月25日

  • 6
    @ 2023-10-29 15:18:09

    C2每课一题解（第四课 第二题）！！！

    这题需用枚举做法（提示：不用long long+优化）。

    话不多说，上代码！

    AC Code

    #include <bits/stdc++.h>
using namespace std;
int a, b, c, d, n;
int main()
{
    cin >> n;
    for(a = 0; a * a <= n / 4; a++)
        for(b = a; b * b <= n / 3; b++)
            for(c = b; c * c <= n / 2; c++)
                for(d = c; d * d <= n; d++)
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
                        return 0;//优化  
                    }
}
    • 3
      @ 2023-6-3 20:52:07

      思路：应该都会

      for(a=0;a*a<=n/4;a++)
	{
			for(b=0;b*b<=n/3;b++)
		{
				for(c=0;c*c<=n/2;c++)
			{
					for(d=0;d*d<=n;d++)
				{
					if(a*a+b*b+c*c+d*d==n)
					{
						cout<<a<<" "<<b<<" "<<c<<" "<<d;
					}
				}
			}
		}
	}

      然鹅……image 一定要加return 0！ 最后，这样就行了。

      #include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n,a,b,c,d;
	cin>>n;
	for(a=0;a*a<=n/4;a++)
	{
			for(b=0;b*b<=n/3;b++)
		{
				for(c=0;c*c<=n/2;c++)
			{
					for(d=0;d*d<=n;d++)
				{
					if(a*a+b*b+c*c+d*d==n)
					{
						cout<<a<<" "<<b<<" "<<c<<" "<<d;
                        return 0;
					}
				}
			}
		}
	}
}
      • 2
        @ 2023-10-29 21:31:33 
        #include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i*i<=n/4;i++){
        for(int j=0;j*j<=n/3;j++){
            for(int k=0;k*k<=n/2;k++){
                for(int r=0;r*r<=n;r++){
                    if(i*i+j*j+k*k+r*r==n){
                        cout<<i<<" "<<j<<" "<<k<<" "<<r<<" ";
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}
        • 2
          @ 2023-8-16 13:14:00 
          #include<bits/stdc++.h>
using namespace std;
long long a;
int main()
{
	cin>>a;
	for(long long i=0;i*i<=a/4;i++)
	{
		for(long long j=0;j*j<=a/3;j++)
		{
			for(long long k=0;k*k<=a/2;k++)
			{
				for(long long h=1;h*h<=a;h++)
				{
					if(h*h+k*k+j*j+i*i==a)
					{
						cout<<i<<" "<<j<<" "<<k<<" "<<h;
						return 0;
					}
				}
			}
		}
	}

          小心：用long long！！！！！！！！！！！！

          • @ 2023-8-16 13:17:56

            不用longlong的话 image 会让自己后悔哦。(～o￣3￣)～hetao2940092。

        • 2
          @ 2023-7-30 18:16:37

          前面几位讲的挺好的，但是数据再大时容易TLE，我的建议是最后一层循环用二分（其实可以全部用二分，但是有点麻烦，数据再大可以写），代码在下面，凑合着看吧

          #include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for (long long i = 0;i <= sqrt(n/4);i++)
    {
        for (long long j = i;j <= sqrt(n/3);j++)
        {
            for (long long k = j;k <= sqrt(n/2);k++)
            {
                int l = k,r = sqrt(n)+1,mid;
                while (l <= r)
                {
                    mid = (l+r)/2;
                    if (pow(i,2)+pow(j,2)+pow(k,2)+pow(mid,2) == n)
                    {
                        cout << i << " " << j << " " << k << " " << mid;
                        return 0;
                    }
                    else
                    {
                        if (pow(i,2)+pow(j,2)+pow(k,2)+pow(mid,2) > n)
                        {
                            r = mid - 1;
                        }
                        else
                        {
                            l = mid + 1;
                        }
                    }
                }
            }
        }
    }
    return 0;
}
          • 2
            @ 2023-7-27 14:34:17

            P1011

            -题目回顾-

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

            每个正整数都可以表示为至多 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 为联合主键升序排列，最后输出第一个表示法。

            #include <bits/stdc++.h>
using namespace std;
long a, b, c, d, n;//一定要long long!
int main()//by AGOMG
{
    cin >> n;
    for(a = 0; a * a <= n / 4; a++)
        for(b = a; b * b <= n / 3; b++)
            for(c = b; c * c <= n / 2; c++)
                for(d = c; d * d <= n; d++)
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
                        return 0;//这里要求输出第一组即可，因此在这里加入return 0
                    }
}
            • 1
              @ 2024-6-11 21:58:45 
              上代码
#include <iostream>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for(long long a = 0;a * a <= n / 4;a++)
    {
        for(long long b = 0;b * b <= n / 3;b++)
        {
            for(long long c = 0;c * c <= n / 2;c++)
            {
                for(long long d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}
看完点个👍
              • 1
                @ 2024-6-3 22:01:36

                P1011 四平方和

                题目描述

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

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

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

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

                要求你对 4 个数排序使得 ​0​≤​a​≤​b​≤​c​≤​d​。

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

                思路 这样谁都会

                for(a=0;a*a<=n/4;a++)
	{
			for(b=0;b*b<=n/3;b++)
		{
				for(c=0;c*c<=n/2;c++)
			{
					for(d=0;d*d<=n;d++)
				{
					if(a*a+b*b+c*c+d*d==n)
					{
						cout<<a<<" "<<b<<" "<<c<<" "<<d;
					}
				}
			}
		}
	}

                但是事情不会总是很完美……你会发现全是TLE 所以……优化代码！

                for(int a = 0;a * a <= n / 4;a++)
    {
        for(int b = 0;b * b <= n / 3;b++)
        {
            for(int c = 0;c * c <= n / 2;c++)
            {
                for(int d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                    }
                }
            }
        }
    }

                给a b c d 都来个上限 but……还是TLE! 为啥，你猜？找到结果了，就return 0呗

                for(int a = 0;a * a <= n / 4;a++)
    {
        for(int b = 0;b * b <= n / 3;b++)
        {
            for(int c = 0;c * c <= n / 2;c++)
            {
                for(int d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }

                but…… 这次还好，9个对的，有一个TLE 上long long!

                #include <bits/stdc++.h>//hetao13565877
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for(long long a = 0;a * a <= n / 4;a++)
    {
        for(long long b = 0;b * b <= n / 3;b++)
        {
            for(long long c = 0;c * c <= n / 2;c++)
            {
                for(long long d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}
                • 0
                  @ 2024-6-2 11:37:49

                  四平方和

                  审题

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

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

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

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

                  要求你对 4 个数排序使得 ​0​≤​a​≤​b​≤​c​≤​d​。

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

                  思路

                  判断都会吧？一一枚举就行

                  代码

                  for(int a = 0;a * a <= n / 4;a++) { for(int b = 0;b * b <= n / 3;b++) { for(int c = 0;c * c <= n / 2;c++) { for(int d = 0;d * d <= n;d++) { if(a * a + b * b + c * c + d * d == n) { cout << a << " " << b << " " << c << " " << d; return 0; } } } } }

                  彩蛋

                  谢谢观看😁 冷知识：仓鼠超能喝酒 快和家人朋友们炫一炫吧！

                  • 0
                    @ 2024-1-6 17:27:45 
                    #include <iostream>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for(long long a = 0;a * a <= n / 4;a++)
    {
        for(long long b = 0;b * b <= n / 3;b++)
        {
            for(long long c = 0;c * c <= n / 2;c++)
            {
                for(long long d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}
                    • 0
                      @ 2023-10-30 19:09:04 
                      #include <bits/stdc++.h>
using namespace std;
int main()
{
    unsigned long long num;
    cin>>num;
    int dd=sqrt(num);
    for (long long a=0;a<=dd;a++){
        for (long long b=0;b<=dd;b++){
            for (long long c=0;c<=dd;c++){
                for (long long d=1;d<=dd;d++){
                    if (a*a+b*b+c*c+d*d==num){
                        cout<<a<<" "<<b<<" "<<c<<" "<<d;
                        return 0;
                    }
                }
            }
        }
    }
}//会超时一个
                      • -1
                        @ 2024-3-15 19:50:52 
                        #include <iostream>//hetao819473
using namespace std;
int main()
{
    long long n;
    cin >> n;
    for(long long a = 0;a * a <= n / 4;a++)
    {
        for(long long b = 0;b * b <= n / 3;b++)
        {
            for(long long c = 0;c * c <= n / 2;c++)
            {
                for(long long d = 0;d * d <= n;d++)
                {
                    if(a * a + b * b + c * c + d * d == n)
                    {
                        cout << a << " " << b << " " << c << " " << d;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}
                        • -1
                          @ 2023-2-28 15:28:22
                          思路 这道题比较简单，就注意a,b,c,d的上下限就行。由于a是最小的，所以a的平方不会超过n的四分之一，同理b的平方不会超过n的三分之一，c的平方不会超过n的二分之一，d的平方不会超过n。
                          代码 
                          
#include <iostream>
#include <algorithm>
using namespace std;
int n, a, b, c, d;
int main()
{
    cin >> n;
    for(int a = 0; a * a <= n / 4; a++)
        for(int b = a; b * b <= n / 3; b++)
            for(int c = b; c * c <= n / 2; c++)
                for(int d = c; d * d <= n; d++)
                    {
                        if((a * a + b * b + c * c + d * d) == n)
                        {
                            cout << a << " " << b << " " << c << " " << d;
                            return 0;
                        }
                    }
    return 0;//完美AC~
}
                          • -3
                            @ 2023-11-11 23:01:19

                            题目描述

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

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

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

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

                            要求你对 4 个数排序使得 0≤a≤b≤c≤d。

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

                            思路

                            其实很多大佬的代码都挺好的，然而我这有一个for循环的究极优化（优化数的范围，极大缩短时间）：

                            int sn=sqrt(n);//当n为完全平方数时，四数其中之一(即d)最大，其值为根号n，其余值为0，所以上限如此取
    for(int a=0;a<=sn;a++)
    {
        for(int b=a;b<=sn;b++)//要求从小到大输出，所以b>=a，下面类似
        {
            for(int c=b;c<=sn;c++)
            {
                int dd=n-a*a-b*b-c*c;//其值为d的平方，下面检查其是否为完全平方数即可(因为只当dd为完全平方数时d才是整数，且a,b,c从最小开始枚举，所以若有d即此为第一解)
                if(check(dd))//然后输出

                            check函数的内容检查一个整数是否为完全平方数，是则返回true，否则返回false，这个不是重点咱就不教啦。

                            第一次写题解，有不周请见谅。

                            • -4
                              @ 2023-10-6 12:10:34

                              重点：优化+long long

                              #include <iostream>
using namespace std;
int main()
{
long long n;
cin >> n;
for(long long a = 0;a * a <= n / 4;a++)
{
for(long long b = 0;b * b <= n / 3;b++)
{
for(long long c = 0;c * c <= n / 2;c++)
{
for(long long d = 0;d * d <= n;d++)
{
if(a * a + b * b + c * c + d * d == n)
{
cout << a << " " << b << " " << c << " " << d;
}
return 0;
}
                              • -5
                                @ 2023-3-25 0:21:54 
                                #include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i*i<=n;i++)
        for(int j=0;j*j<=n;j++)
        for(int k=0;k*k<=n;k++){
            if(sqrt(n-i*i-j*j-k*k)!=floor(sqrt(n-i*i-j*j-k*k))) continue;
            int l=floor(sqrt(n-i*i-j*j-k*k));
            if(i*i+j*j+k*k+l*l==n){
                cout<<i<<" "<<j<<" "<<k<<" "<<l;
                return 0;
            }
        }
}
                                • -7
                                  @ 2023-8-6 21:53:39 
                                  #include <cstdio>
using namespace std;
int main(){
    long long n;
    scanf("%ld",&n);
    for(long long i=0;i*i<=n/4;i++){
        for(long long j=0;j*j<=n/3;j++){
            for(long long k=0;k*k<=n/2;k++){
                for(long long l=0;l*l<=n;l++){
                    if(i*i+j*j+k*k+l*l==n){
                        printf("%ld %ld %ld %ld\n",i,j,k,l);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}
                                  • 1

                                  四平方和

                                  信息

                                  ID
                                  50
                                  时间
                                  1000ms
                                  内存
                                  256MiB
                                  难度
                                  5
                                  标签
                                  递交数
                                  3387
                                  已通过
                                  1374
                                  上传者
                                  1. 关于
                                  2. 联系我们
                                  3. 隐私
                                  4. 服务条款
                                  5. 版权申诉
                                  6. Language
                                  7. 兼容模式
                                  8. 主题
                                  3. Worker 0, 28ms
                                  4. Powered by Hydro v4.9.24 Community, Modified by hetao