首页 > 代码库 > 四平方和书

四平方和书

2024-09-03 21:23:07   218人阅读

给定一个小于5000000的数，将之分解为至多4个数的平方和。

技术分享
#include<bits/stdc++.h>#define maxn 5000005using namespace std;bool a2b2[maxn];int main(){    memset(a2b2,0,sizeof(a2b2));    for(int i=0;i*i<maxn;i++)    {        for(int j=0;j*j<maxn;j++)        {            int tmp=i*i+j*j;            if(tmp<maxn)            {                a2b2[tmp]=true;            }        }    }    int n;    cin>>n;    for(int i=0;i*i<=n;i++)    {        for(int j=0;j*j<=n;j++)        {            int tmp=i*i+j*j;            if (tmp>n) continue;            if(!a2b2[n-tmp]) continue;            int res=n-tmp;            for(int k=0;k*k<=res;k++)            {                int l=res-k*k;                if(l-(int)sqrt(l)*(int)sqrt(l)==0)                {                    l=(int)sqrt(l);                    int ans[4]={i,j,k,l};                    sort(ans,ans+4);                    for(int t=0;t<3;t++)                        cout<<ans[t]<<" ";                    cout<<ans[3]<<endl;                    return 0;                }            }        }    }    return 0;}
View Code

这里有一个拉格朗日定理：每个正整数都可以表示为至多 

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

 

 

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 44 个正整数的平方和。如果把 00 包括进去，就正好可以表示为 44 个数的平方和。

比如：

 

\displaystyle 5 = 0^2 + 0^2 + 1^2 + 2^25=0?2??+0?2??+1?2??+2?2??

 

 

\displaystyle 7 = 1^2 + 1^2 + 1^2 + 2^27=1?2??+1?2??+1?2??+2?2??

 

则对于一个给定的正整数 nn，可以表示为：n = a^2 + b^2 + c^2 + d^2n=a?2??+b?2??+c?2??+d?2??。

你需要求出字典序最小的一组解 a,b,c,da,b,c,d。

字典序大小：从左到右依次比较，如果相同则比较下一项，直到有一项不同，较小的一方字典序更小，反之字典序更大，所有项均相同则二者字典序相同。

输入格式

程序输入为一个正整数 N(1 \leq N \leq 5000000)N(1≤N≤5000000)。

输出格式

输出 44 个非负整数 a,b,c,da,b,c,d，中间用空格分开。

样例输入1

5

样例输出1

0 0 1 2

样例输入2

12

样例输出2

0 2 2 2
    • main.cpp
  
 
 
 
 
 
 
1
#include<bits/stdc++.h>
2
#define maxn 5000005
3
using namespace std;
4
bool a2b2[maxn];
5
int main()
6
{
7
    memset(a2b2,0,sizeof(a2b2));
8
    for(int i=0;i*i<maxn;i++)
9
    {
10
        for(int j=0;j*j<maxn;j++)
11
        {
12
            int tmp=i*i+j*j;
13
            if(tmp<maxn)
14
            {
15
                a2b2[tmp]=true;
16
            }
17
        }
18
    }
19
    int n;
20
    cin>>n;
21
    for(int i=0;i*i<=n;i++)
 
 
 
重做历史

 

四平方和书


联系
我们