题目描述

四平方和定理,又称为拉格朗日定理:

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

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

比如:

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

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

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

要求你对 4 个数排序:

$0≤a≤b≤c≤d$

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

输入格式

输入一个正整数 N

输出格式

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

数据范围

$0<N<5{\times}10^6$

输入样例:

5

输出样例:

0 0 1 2

算法分析

$a,b,c,d{\leqslant}N=5{\times}10^6$

$\sqrt(N)=2236.067977$故最多只能枚举两位数($2236^{2236} {\geq}1{\times}10^8$)

故:

  1. 最多只能枚举2个数
  2. 空间换时间

第一步:空间换时间方法

for (c = 0; pow(c, 2) <= N; c ++)
    for (d = c; pow(c, 2) + pow(d, 2) <= N; d ++)
        // 存放c^2 + d^2的值

将所有的$c^2+d2$存起来$O(N^2)$

第二步:枚举

for (a = 0; pow(a, 2) <= N; a ++)
    for (b = a; pow(b, 2) + pow(c, 2) <= N; b ++)
        t = n - pow(c, 2) - pow(d, 2);

t表示和最终答案的差是多少$O(N^2)$
此时我们只需要去判断一下这个 t能否用两个数的平方和凑出来即可,
即得到 t寻找前面$c^2+d2$的值,是否存在与t相等的值。

if (存在与t相等的值)
    // 输出answer

寻找方法:

  1. 哈希$O(1)$
  2. 二分$O(logn)$

第三步:找到字典序最小解

分析:对于 ab,是两个 for循环找到的最小的值,因此前两个数可以保证字典序最小。
所以现在我们只需要找到后两个字典序最小的组合即可。
故存放的时候我们不仅要存放$c^2+d^2$的值,还要按照 c,d的字典序排先后顺序。

AC代码

暴力做法:$O(N^3)$ 超时

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

int n;

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

二分查找:$O(N^2logN)$ 2747 ms

#include <bits/stdc++.h>
using namespace std;

const int N = 5 * 1e6 + 10;
int n, x;
int a, b, c, d;


struct val {
    int t, x, y;
};

val V[N];
int m;

bool cmp(val v1, val v2) {
    if (v1.t != v2.t) {
        return v1.t < v2.t;
    } else if (v1.x != v2.x) {
        return v1.x < v2.x;
    } else {
        return v1.t < v2.t;
    }
}


int main() {
  
    scanf("%d", &n);
  
    // 存放放c^2和d^2的值
    for (c = 0; c * c <= n; c ++) {
        for (d = c; c * c + d * d <= n; d ++) {  
            // 使用数组存放c^2和d^2的值和数据
            V[m ++] = {c * c + d * d, c, d};
        }
    }
  
    // 二分查找需要有序
    sort(V, V + m, cmp);

    //枚举
    for (a = 0; a * a <= n; a ++) {
        for (b = a; a * a + b * b <= n; b ++) {
            int t = n - a * a - b * b;
            // 二分查找
            int l = 0, r = m - 1;
            while(l < r) {
                int mid = l + r >> 1;
                if (V[mid].t >= t) r = mid;
                else l = mid + 1;
            }
  
            if (V[l].t == t) {
                printf("%d %d %d %d", a, b, V[l].x, V[l].y);
                exit(0);
            }
        }
    }
    return 0;
}

哈希表$O(N^2)$ 超时

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 2500010;

int n, m;
unordered_map<int, PII> S;

int main()
{
    cin >> n;

    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
        {
            int t = c * c + d * d;
            if (S.count(t) == 0) S[t] = {c, d};
        }

    for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            int t = n - a * a - b * b;
            if (S.count(t))
            {
                printf("%d %d %d %d\n", a, b, S[t].x, S[t].y);
                return 0;
            }
        }

    return 0;
}

大佬使用air数组直接做的 395 ms

#include<iostream>
#include<map>
using namespace std;

const int MAX=5e6+5;
int n;
pair<int,int> a[MAX];

int main()
{
    cin>>n;
    for(int i=0;i*i<=n;i++)
    {
        for(int j=i;i*i+j*j<=n;j++)
        {
             int t=i*i+j*j;
             if(a[t].second==0&&a[t].first==0)
             {
                 a[t]={i,j};
             }
        }
    }
    for(int i=0;i*i<=n;i++)
    {
        for(int j=i;j*j+i*i<=n;j++)
        {
            int t=n-i*i-j*j;
            if(a[t].second!=0||a[t].first!=0)
            {
                cout<<i<<" "<<j<<" "<<a[t].first<<" "<<a[t].second;
                return 0;
            }
        }
    }
    return 0;
}
最后修改:2022 年 02 月 08 日
如果觉得我的文章对你有用,请随意赞赏