import math


class Solution(object):
    def powerfulIntegers(self, x, y, bound):
        """
        :type x: int
        :type y: int
        :type bound: int
        :rtype: List[int]
        """
        res = []
        if not bound:
            return res
        if x == 1 and y == 1:
            if bound >= 2:
                res.append(2)
            return res

        if x > y:
            return self.powerfulIntegers(y, x, bound)

        if x == 1:
            for j in xrange(0, int(math.ceil(math.log(bound, y)))):
                s = x + y ** j
                if s <= bound and s not in res:
                    res.append(s)
        else:
            for i in xrange(0, int(math.ceil(math.log(bound, x)))):
                for j in xrange(0, int(math.ceil(math.log(bound, y)))):
                    s = x ** i + y ** j
                    if s <= bound and s not in res:
                        res.append(s)

        return res


if __name__ == '__main__':
    print Solution().powerfulIntegers(2, 3, 10)
    print Solution().powerfulIntegers(3, 5, 15)
    print Solution().powerfulIntegers(1, 1, 0)
    print Solution().powerfulIntegers(1, 2, 100)
