Chương trình tìm bội số của n chỉ chứa hai chữ số 9 và 0 trong Python

Cho số n. Tìm số dương nhỏ nhất x chỉ chứa chữ số 9 và 0, và x chia hết cho n.

Ví dụ: n = 26 → kết quả 90090.

Thuật toán giải quyết (BFS trên không gian nhị phân)

1. Khởi tạo m = 9, x = 1
2. Khi m % n != 0:
   • x += 1
   • m = int(bin(x)[2:].replace('1', '9')) (chuyển x sang nhị phân, thay 1→9, 0→0)
3. Trả về m

Ý tưởng: mọi số chỉ chứa 9 và 0 tương ứng với một số nhị phân (1→9, 0→0). Duyệt x = 1,2,3... sinh ra tất cả các số dạng đó theo thứ tự tăng dần.

Ví dụ minh họa

def solve(n):
    m = 9
    x = 1
    while m % n != 0:
        x += 1
        m = int(bin(x)[2:].replace('1','9'))
    return m

n = 26
print(solve(n))

Đầu vào

26

Đầu ra

90090