将数字N重新排序，成为可被M整除的最大数字

Question

假设我有数字 N，带有

1 <= N <= 10^15

。我想重新排序数字，以便获得尽可能最小的数字，并且它可以被 M 整除。

例如：N = 4264，M = 8 那么N的数字所组成的最大能被M整除的数是6424

这是我的代码：

n = int(input())
m = int(input())
s = list(map(int,list(str(n))))
s.sort(reverse=True)
# missing part here
print("".join(map(str, s)))

我缺少对 N 的数字重新排序的部分。 有人可以帮助我吗？

Answer 1

您只需定义一个函数来检查数字能否被给定整数整除：

import itertools

def smallest_divisible_by_m(digits, m):
    digits.sort()
    for perm in itertools.permutations(digits):
        if perm[0] == 0:
            continue
        num = int(''.join(map(str, perm)))
        if num % m == 0:
            return num
    return None  
n = int(input("Enter N: "))
m = int(input("Enter M: "))

digits = list(map(int, str(n)))

result = smallest_divisible_by_m(digits, m)
if result is not None:
    print("The smallest number formed by the digits of", n, "that is divisible by", m, "is", result)
else:
    print("No valid number formed by the digits of", n, "is divisible by", m)

这是示例的输出：