# 970. Powerful Integers 强整数

@TOC

## # 题目描述

Given two non-negative integers `x` and `y`, an integer is powerful if it is equal to `x^i + y^j` for some integers `i >= 0` and `j >= 0`.

Return a list of all powerful integers that have value less than or equal to `bound`.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

``````Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
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
``````

Example 2:

``````Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]
``````

Note:

1. 1 <= x <= 100
2. 1 <= y <= 100
3. 0 <= bound <= 10^6

## # 解题方法

### # 暴力搜索

python代码如下：

``````class Solution(object):
def powerfulIntegers(self, x, y, bound):
"""
:type x: int
:type y: int
:type bound: int
:rtype: List[int]
"""
res = set()
i = 0
while x ** i <= bound and i <= bound:
j = 0
while j <= bound:
target = x ** i + y ** j
if target > bound:
break
j += 1
i += 1
return list(res)
``````

C++代码如下：

``````class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
set<int> res;
for (int i = 1; i < bound; i *= x) {
for (int j = 1; i + j <= bound; j *= y) {
res.insert(i + j);
if (y == 1) break;
}
if (x == 1) break;
}
return vector<int>(res.begin(), res.end());
}
};
``````

## # 日期

2019 年 1 月 6 日 —— 打球打的腰酸背痛