Given $N,M$ and $D$ we need to count how many permutations of $N$ integers are there with each $i$'th element $1 \le A[i] \le M$ such that least common multiple (LCM) of all its elements is divisible by number $D$.
Here $M$ is at max $1000$ and $N$ can go up to $10^6$.
How to approach this question? Please help as i can't even think of how to start it.So some ideas will be very helpful to tackle this problem.
Can their be direct formula for this question ? Assuming I am have prime factorisation of $D$.
A hint to get you started: If you factor $D$, at least one of the $A$'s has to account for each of the prime powers that divide $D$. So for $D=600=2^3\cdot3\cdot 5^2$, at least one of the $A$'s must be divisible by $2^3$, at least one (maybe the same one) must be divisible by $3$, and one must be divisible by $5^2$ If you imagine a three circle Venn diagram, each region represents one class of factors. One class will have a factor $2^3$ and $3$ but not $5^2$ for example. Figure out how many numbers are in each class. If $A[1]$ is from that class, you only need a factor of $5^2$ from one of the rest. You can use dynamic programming, calling with $N-1$ and the remaining $D$
Added: here is a small example. Let $N=4, D=6, M=12$. As $6=2\cdot 3$ the divisibility classes are $1,2,3,6$. Class $6$ includes $6,12$. Class $3$ includes $3,9$. If $A[1]$ is from class $6$, the rest can be anything, so this contributes $2 \cdot 12^3$ possibilities. If $A[1]$ is from class $3$, at least one of the rest has to be even, so this contributes $2$ times the solution with $N=3,D=2,M=12$