Number of permutation of a particular string is divisible by a number

Question

Suppose I have a multiset of 10 digits, for example S = { 1, 1, 2, 2, 2, 3, 3, 3, 8, 9 }. Is there any method other than brute force to find the number of distinct permutations of the elements of S such that when a permutation is regarded as a ten digit integer, it is divisible by a particular number n ? n will be in the range 1 to 10000.

For example:

if S = { 1, 2, 3, 4, 6, 1, 2, 3, 4, 6 } and n = 10, the result is 0 (since no permutation of those 10 digits will ever give a number divisible by 10)

if S = { 1, 1, 3, 3, 5, 5, 7, 7, 9, 2} and n = 2, the result is 9! / 2^4 (since we must have the 2 at the end, there are 9! ways to permute the other elements, but there are four pairs of identical elements)

Answer 1

You could prune the search like so: find the prime factorization of NUM. Obviously to be divisible by NUM, a permutation needs to be divisible by all of NUM's prime factors. Hence you can use simple divisibility rules to avoid generating many invalid candidates.