更多精彩内容，请关注【力扣简单题】。

题目

难度：★★☆☆☆
类型：数学，排列组合

给定两个正整数 x 和 y，如果某一整数等于 x^i + y^j，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个强整数。

返回值小于或等于 bound 的所有强整数组成的列表。

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

提示
1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

示例

示例 1
输入：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

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

解答

这道题的难点在于如何进行i和j的搜索。我们可以使用类似穷举法的方式，找到所有可能的(i, j)组合，注意这里的i和j有可能相等，并且从零开始，上限需要我们寻找。

如何寻找上限？我们首先需要设置(i, j)搜索范围，这与输入的两个数字x和y有关，为了寻找尽可能全面，我们需要选出以边界bound为底，分别以x和y为幂的对数log(bound, x)和log(bound, y)中的较大值，并且取整，因此搜索范围初步定为从0到int(log(bound, min(x, y)))（含）。

举个栗子，如果输入x=2，y=3，bound=10，搜索空间的上限是int(min(log(10, 2), log(10, 3)))+1 = int(log(10, min(2, 3)))+1=int(log(10, 2))+1 = int(3.32...) = 3，i和j的搜索范围是[0, 1, 2, 3]，在python中表示为list(range(4))。（注意这里是左闭右开的区间）

python中product(list, repeat=2)可以返回列表自身与自身元素组成的笛卡尔积元组，上述(i, j)元素的搜索范围可以表示为product(range(4), repeat=2)，这时会生成一个迭代器，迭代会获得下面的(i, j)元组：

0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3

这些i，j囊括了不大于bound的所有pow(x, i)+pow(y, i)可能，我们要做的从其中选择出能使pow(x, i)+pow(y, i)不大于bound的所有可能。

这里有一个问题需要注意，就是log(b, a)（计算以b为底a的对数）函数的输入参数存在合法范围，a不能小于1，b不能小于2，因此我们使用max()函数对输入进行下限的限制：log(max(b, 1), max(a))。

from itertools import product
from math import log


class Solution:
    def powerfulIntegers(self, x, y, bound):
        """
        :param x: int
        :param y: int
        :param bound: int
        :return: List[int]
        """
        res = []
        rg = int(log(max(bound, 1), min(max(x, 2), max(y, 2))))+1
        for i, j in product(range(rg), repeat=2):
            num = x ** i + y ** j
            if num <= bound:
                res.append(num)
        return list(set(res))

如有疑问或建议，欢迎评论区留言~