Số nguyên mạnh (Powerful Integers) trong Python

Giả sử ta có hai số nguyên dương x và y, ta nói số nguyên mạnh nếu nó bằng x^i + y^j với i >= 0 và j >= 0. Ta tìm list tất cả số mạnh giá trị <= bound.

Ví dụ, x=2, y=3, bound=10, đầu ra [2,3,4,5,7,9,10], vì 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.

Giải quyết theo các bước:

• Khởi tạo a,b = 0
• res := list mới
• if x==1 and y==1, then
  • if bound>=2, thêm 2 vào res
• else if x==1, then
  • while y^b+1 <= bound, thêm y^b+1 vào res, b+=1
• else if y==1, then
  • while x^a+1 <= bound, thêm x^a+1 vào res, a+=1
• else
  • while x^a+1 <= bound, do
    • if x^a+y^b <= bound, thêm vào res, b+=1
    • else a+=1, b=0

Xem triển khai:

Ví dụ

class Solution:
    def powerfulIntegers(self, x, y, bound):
        a, b = 0, 0
        res = []
        if x == 1 and y == 1:
            if bound >= 2:
                res.append(2)
        elif x == 1:
            while y**b + 1 <= bound:
                res.append(y**b + 1)
                b += 1
        elif y == 1:
            while x**a + 1 <= bound:
                res.append(x**a + 1)
                a += 1
        else:
            while x**a + 1 <= bound:
                if x**a + y**b <= bound:
                    res.append(x**a + y**b)
                    b += 1
                else:
                    a += 1
                    b = 0
        return list(set(res))
ob = Solution()
print(ob.powerfulIntegers(2, 3, 10))

Đầu vào

2,3,10

Đầu ra

[2, 3, 4, 5, 7, 9, 10]