跳转至

3890. 可由多种立方和构造的整数

题目描述

给你一个整数 n。

当存在 至少 两组不同的整数对 (a, b) 满足以下条件时，整数 x 被称为 好整数：

  • a 和 b 是正整数。
  • a <= b
  • x = a3 + b3

返回一个数组，其中包含所有小于等于 n 的好整数，并按升序排序。

 

示例 1：

输入： n = 4104

输出： [1729,4104]

解释：

在小于等于 4104 的整数中，好整数包括：

  • 1729：13 + 123 = 1729，以及 93 + 103 = 1729。
  • 4104：23 + 163 = 4104，以及 93 + 153 = 4104。

因此，答案是 [1729, 4104]。

示例 2：

输入： n = 578

输出： []

解释：

不存在小于等于 578 的好整数，因此答案是空数组。

 

提示：

  • 1 <= n <= 109

解法

方法一：预处理 + 二分查找

我们注意到，当 \(a\) 或 \(b\) 大于 \(1000\) 时，式子 \(a^3 + b^3 > 10^9\)。因此，我们只需要枚举 \(1 \leq a \leq b \leq 1000\)，统计每个整数 \(x = a^3 + b^3\) 的出现次数。最后，筛选出出现次数大于 \(1\) 的整数，并按升序排序，得到所有的好整数。

我们将所有好整数预处理出来，存储在数组 \(\textit{GOOD}\) 中。对于每个查询，我们使用二分查找找到 \(\textit{GOOD}\) 中第一个大于 \(n\) 的整数的索引 \(idx\)，返回 \(\textit{GOOD}\) 中前 \(idx\) 个整数即可。

时间复杂度为 \(O(m^2 + k \log k)\)，其中 \(m = 1000\) 是枚举的范围，而 \(k\) 是好整数的数量。空间复杂度为 \(O(k)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
LIMIT = 10**9

cnt = defaultdict(int)
cubes = [i**3 for i in range(1001)]

for a in range(1, 1001):
    for b in range(a, 1001):
        x = cubes[a] + cubes[b]
        if x > LIMIT:
            break
        cnt[x] += 1

GOOD = sorted(x for x, v in cnt.items() if v > 1)


class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        idx = bisect_right(GOOD, n)
        return GOOD[:idx]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private static final int LIMIT = (int) 1e9;
    private static final List<Integer> GOOD = new ArrayList<>();

    static {
        Map<Integer, Integer> cnt = new HashMap<>();
        int[] cubes = new int[1001];
        for (int i = 0; i <= 1000; i++) {
            cubes[i] = i * i * i;
        }
        for (int a = 1; a <= 1000; a++) {
            for (int b = a; b <= 1000; b++) {
                int x = cubes[a] + cubes[b];
                if (x > LIMIT) {
                    break;
                }
                cnt.merge(x, 1, Integer::sum);
            }
        }
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            if (e.getValue() > 1) {
                GOOD.add(e.getKey());
            }
        }

        Collections.sort(GOOD);
    }

    public List<Integer> findGoodIntegers(int n) {
        int idx = Collections.binarySearch(GOOD, n + 1);
        if (idx < 0) {
            idx = -idx - 1;
        }
        return GOOD.subList(0, idx);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<int> GOOD;

auto init = [] {
    const int LIMIT = 1e9;

    unordered_map<int, int> cnt;
    vector<int> cubes(1001);

    for (int i = 0; i <= 1000; ++i) {
        cubes[i] = i * i * i;
    }

    for (int a = 1; a <= 1000; ++a) {
        for (int b = a; b <= 1000; ++b) {
            int x = cubes[a] + cubes[b];
            if (x > LIMIT) break;
            cnt[x]++;
        }
    }

    for (auto& [x, v] : cnt) {
        if (v > 1) {
            GOOD.push_back(x);
        }
    }

    sort(GOOD.begin(), GOOD.end());

    return 0;
}();

class Solution {
public:
    vector<int> findGoodIntegers(int n) {
        int idx = upper_bound(GOOD.begin(), GOOD.end(), n) - GOOD.begin();
        return vector<int>(GOOD.begin(), GOOD.begin() + idx);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var GOOD []int

func init() {
    const LIMIT = 1e9

    cnt := make(map[int]int)
    cubes := make([]int, 1001)

    for i := 0; i <= 1000; i++ {
        cubes[i] = i * i * i
    }

    for a := 1; a <= 1000; a++ {
        for b := a; b <= 1000; b++ {
            x := cubes[a] + cubes[b]
            if x > LIMIT {
                break
            }
            cnt[x]++
        }
    }

    for x, v := range cnt {
        if v > 1 {
            GOOD = append(GOOD, x)
        }
    }

    sort.Ints(GOOD)
}

func findGoodIntegers(n int) []int {
    idx := sort.Search(len(GOOD), func(i int) bool {
        return GOOD[i] > n
    })
    return GOOD[:idx]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const LIMIT = 1e9;

const GOOD: number[] = (() => {
    const cnt = new Map<number, number>();
    const cubes: number[] = Array.from({ length: 1001 }, (_, i) => i * i * i);

    for (let a = 1; a <= 1000; a++) {
        for (let b = a; b <= 1000; b++) {
            const x = cubes[a] + cubes[b];
            if (x > LIMIT) break;
            cnt.set(x, (cnt.get(x) ?? 0) + 1);
        }
    }

    const res: number[] = [];
    for (const [x, v] of cnt.entries()) {
        if (v > 1) res.push(x);
    }

    res.sort((a, b) => a - b);
    return res;
})();

function findGoodIntegers(n: number): number[] {
    const idx = _.sortedLastIndex(GOOD, n);
    return GOOD.slice(0, idx);
}

评论