【Leetcode】970. Powerful Integers

题目地址：

https://leetcode.com/problems/powerful-integers/

给定两个正整数$x,y$和一个非负整数$b$，求 { z = x i + y j ∣ z ≤ b , i ≥ 0 , j ≥ 0 } \{z=x^i+y^j|z\le b, i\ge 0, j\ge 0\} {z=xi+yj∣z≤b,i≥0,j≥0}。

直接暴力枚举即可。代码如下：

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

    return vector<int>(set.begin(), set.end());
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时空复杂度$O({\log }_{x}b{\log }_{y}b)$。