Kiểm tra hoán vị chữ số của N có bằng lũy thừa của K trong Python

Cho hai số nguyên dương n và m (2 ≤ n ≤ 10^18, 2 ≤ m ≤ n). Kiểm tra xem có tồn tại một hoán vị của các chữ số của n bằng một lũy thừa của m hay không.

Ví dụ: n=7182, m=12 → 1728 là hoán vị của 7182 và 1728 = 12^3 → "An all digit-permutation of n is equal to a power of m".

Giải thuật

• Hàm check_power(n, m) so sánh tập hợp chữ số của n và m (bỏ qua thứ tự).
• Tính trước các lũy thừa của m cho đến 10^18.
• Kiểm tra từng lũy thừa với check_power.

Mã ví dụ

def check_power(n, m):
    temp_arr_1 = []
    temp_arr_2 = []
    while n > 0:
        temp_arr_1.append(n % 10)
        n //= 10
    while m > 0:
        temp_arr_2.append(m % 10)
        m //= 10
    if set(temp_arr_1) == set(temp_arr_2):
        return True
    return False

def solve(n, m):
    power_array = [0] * 100
    max_range = pow(10, 18)
    power_array[0] = m
    i = 1
    while power_array[i - 1] * m < max_range:
        power_array[i] = power_array[i - 1] * m
        i += 1
    for j in range(i):
        if check_power(n, power_array[j]):
            return "An all digit-permutation of n is equal to a power of m"
    return "No all digit-permutation of n is equal to a power of m"

n, m = 7182, 12
print(solve(n, m))

Đầu vào

7182, 12

Đầu ra

An all digit-permutation of n is equal to a power of m