Количество перестановок конкретной строки делится на число

Question

Предположим, у меня есть мультимножество из 10 цифр, например S = { 1, 1, 2, 2, 2, 3, 3, 3, 8, 9 }.Есть ли другой метод, кроме грубой силы, чтобы найти число различных перестановок элементов S, чтобы при перестановке рассматривать как целое из десяти цифр, оно делилось на конкретное число n?n будет в диапазоне от 1 до 10000.

Например:

, если S = { 1, 2, 3, 4, 6, 1, 2, 3, 4, 6 } и n = 10, результат равен 0 (поскольку перестановка отсутствуетиз этих 10 цифр получим число, кратное 10)

, если S = { 1, 1, 3, 3, 5, 5, 7, 7, 9, 2} и n = 2, результат равен 9! / 2^4 (поскольку в конце мы должны иметь 2, есть 9! способов перестановки других элементов, но есть четыре пары идентичных элементов)

Answer 1

У меня есть некоторые мысли, но они не организованы в настоящий алгоритм.

Для N = 2 мы просто видим, сколько четных цифр мы можем положить в конец наших перестановок, и таким образом вычисляем число.

Для N = 3 мы знаем, что сумма цифр должна делиться на 3. Это означает, что мы можем свободно помещать любые 3 с, 6 с, 9 с и 0 в наши перестановки, но любые другие цифры, которые мы должны поставить в парах, которые составляют 3, 6 или 9 (или триплет из 1 с). Я не думаю, что это будет слишком сложно реализовать.

Для N = 4 мы можем сделать что-то похожее на N = 2.

Я думаю, что мы можем придумать такие случаи до N = 10 (N = 7 может быть сложным). Тогда мы можем сделать любое N> 10, разложив его на множители. Например, если N = 18, любые перестановки, которые делятся на N, также делятся на 2 и 9. Конечно, если N - простое число, у нас могут быть проблемы.

Answer 2

Вы можете сократить поиск следующим образом: найти простую факторизацию NUM.Очевидно, что для деления на NUM, перестановка должна делиться на все основные факторы NUM.Следовательно, вы можете использовать простые правила делимости , чтобы избежать создания множества недопустимых кандидатов.

Answer 3

Моя идея: сортировать цифры S по возрастанию и убыванию. Теперь у вас есть min и max, которые можно сгенерировать из S. Теперь возьмите все кратные N в интервале min, max и посмотрите, какие из них образованы цифрами в S.