970. Powerful Integers

Given two positive 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 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

这题给我们两个数，还有一个作为边界的数字。我们对前两个数分别求次方，它们的结果的和假设在边界范围内，就可以认为是符合条件的数字，可以加入结果集当中。

这题直接爆破即可，需要注意的是，假设两个数字有1的情况，需要特殊处理，不然可能会死循环。

class PowerfulIntegers : public Solution {
public:
    void Execute() {

    }

    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> res;

        int64_t lv = 1;
        for (;;) {
            int64_t rv = 1;
            for (;;) {
                int64_t value = lv + rv;
                if (value <= bound) {
                    res.insert(value);
                } else if (value > bound) {
                    break;
                }
                if (y == 1) {
                    break;
                }
                rv *= y;
            }
            lv *= x;
            if (lv > bound || x == 1) {
                break;
            }
        }

        return vector<int>(res.begin(), res.end());
    }
};