侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【哈希表】四平方和【蓝桥杯】

GabrielxD
2022-09-11 / 0 评论 / 0 点赞 / 520 阅读 / 1,322 字
温馨提示:
本文最后更新于 2023-02-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 历届真题 四平方和【第七届】【省赛】【C组】

四平方和 - 蓝桥云课

1221. 四平方和


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

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

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

比如:

5=02+02+12+225 = 0^2 + 0^2 + 1^2 + 2^2
7=12+12+12+227 = 1^2 + 1^2 + 1^2 + 2^2

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

要求你对 44 个数排序:

0abcd0 \le a \le b \le c \le d

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

输入格式

输入一个正整数 NN

输出格式

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

数据范围

0<N<5×1060 < N < 5 \times 10^6

输入样例:

5

输出样例:

0 0 1 2

解题

方法一:暴力 枚举(超时)

思路

从大到小暴力枚举 dcba 的所有可能值,找到第一个符合 a * a + b * b + c * c + d * d == N 的结果返回。

时间复杂度为 O(n4)O(n^4)5×1065\times10^6 的数据规模下必定超时。

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int N = (int) in.nval;
        for (int d = N / 2; d > 0; --d) {
            for (int c = d; c >= 0; --c) {
                for (int b = c; b >= 0; --b) {
                    for (int a = b; a >= 0; --a) {
                        if (a * a + b * b + c * c + d * d == N) {
                            System.out.printf("%d %d %d %d\n", a, b, c, d);
                            return;
                        }
                    }
                }
            }
        }
    }
}

只枚举 dcb ,最后算出 a 判断是否合法。
这样做可以把时间复杂度降到 O(n3)O(n^3),但是还是会超时。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int N = (int) in.nval;
        for (int d = N / 2; d > 0; --d) {
            for (int c = d; c >= 0; --c) {
                for (int b = c; b >= 0; --b) {
                    int rest = N - (b * b + c * c + d * d);
                    if (rest < 0) continue;
                    int a = (int) Math.sqrt(rest);
                    if (a * a == rest) {
                        System.out.printf("%d %d %d %d\n", a, b, c, d);
                        return;
                    }
                }
            }
        }
    }
}

方法二:枚举 哈希表 二分查找 空间换时间

思路

先枚举 cd 把合法值存入哈希表然后再枚举 ab 找出结果可以把时间复杂度降到 O(n2)O(n^2)。具体做法是:

维护一个哈希表(map),键为 cd 的平方和,值为当 c <= dc * c + d * d <= nc 尽量小 d 尽量大的值,然后双层循环:外层从小到大枚举 c,内层从大到小枚举 d,为保证 c 尽量小 d 尽量大,只取第一次合法的值放入哈希表。

再开一个双层循环:外层从小到大枚举 a,内层从大到小枚举 b,算出 ab 的平方和,如果在哈希表中存在 n 减去 ab 的平方和,就说明找到了一组合法的四平方和的解,因为枚举方式保证了 a 取得尽量小 b 取得尽量大,所以第一组找到的解就是升序最大的解,从哈希表中取出 cd 的值直接返回。

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        Map<Integer, int[]> map = new HashMap<>();
        for (int c = 0; c * c * 2 <= n; ++c) {
            for (int d = c; c * c + d * d <= n; ++d) {
                map.putIfAbsent(c * c + d * d, new int[]{c, d});
            }
        }
        for (int a = 0; a * a * 4 <= n; ++a) {
            for (int b = a; a * a + b * b <= n / 2; ++b) {
                int rest = n - (a * a + b * b);
                if (map.containsKey(rest)) {
                    int[] cd = map.get(rest);
                    System.out.printf("%d %d %d %d\n", a, b, cd[0], cd[1]);
                    return;
                }
            }
        }
    }
}

二分换哈希表:

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        List<int[]> arr = new ArrayList<>();
        for (int c = 0; c * c <= n; ++c) {
            for (int d = c; c * c + d * d <= n; ++d) {
                arr.add(new int[]{c * c + d * d, c, d});
            }
        }
        arr.sort((x, y) -> {
            if (x[0] != y[0]) return x[0] - y[0];
            else if (x[1] != y[1]) return x[1] - y[1];
            else return x[2] - y[2];
        });
        for (int a = 0; a * a * 4 <= n; ++a) {
            for (int b = a; (a * a + b * b) * 2 <= n; ++b) {
                int x = n - (a * a + b * b);
                int l = 0, r = arr.size() - 1;
                while (l < r) {
                    int m = l + r >> 1;
                    if (arr.get(m)[0] >= x) r = m;
                    else l = m + 1;
                }
                if (arr.get(l)[0] == x) {
                    System.out.printf("%d %d %d %d\n", a, b, arr.get(l)[1], arr.get(l)[2]);
                    return;
                }
            }
        }
    }
}
0

评论区