题目描述

给定两个非负整数 x 和 y，一个整数是 有力量的 ，如果存在某个整数 i >= 0 和 j >= 0，它等于 x^i + y^j。

返回一个所有 有力量 数字的列表，其中每个值都小于等于 bound。

你可以以任何顺序返回答案，你的答案中，每个数字最多出现一次。

样例

输入：x = 2, y = 3, bound = 10
输出：[2,3,4,5,7,9,10]
解释：
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

输入：x = 3, y = 5, bound = 15
输出：[2,4,6,8,10,14]

注意

• 1 <= x <= 100
• 1 <= y <= 100
• 0 <= bound <= 10^6

算法

(暴力枚举) $O(\log^2 bound)$

1. 假设 x 和 y 都大于 1，我们定义两个整数 sum1 = x^i 和 sum2 = x^j。再开一个哈希表防止重复。
2. 两层循环，第一层 sum1 从 1 开始累乘 x 直到 sum1 > bound；第二层 sum2 从 1 开始累乘 y 直到 sum1 + sum2 > bound；过程中记录答案。
3. 如果 x 为 1，则在第一层循环结尾直接跳出循环；如果 y 为 1，则在第二层循环结尾跳出循环。

时间复杂度

• 每一层循环最多执行 $O(\log bound)$ 次，故总时间复杂度为 $O(\log^2 bound)$。

空间复杂度

• 哈希表同样占用 $O(\log^2 bound)$ 的空间。

C++ 代码

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> vis;
        vector<int> ans;

        for (int sum1 = 1; sum1 <= bound; sum1 *= x) {
            for (int sum2 = 1; sum1 + sum2 <= bound; sum2 *= y) {
                int sum = sum1 + sum2;
                if (vis.find(sum) != vis.end())
                    continue;
                vis.insert(sum);
                ans.push_back(sum);
                if (y == 1)
                    break;
            }
            if (x == 1)
                break;
        }

        return ans;
    }
};