The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)

I was wondering whether there was a cleaner Dynamic Programming solution.**Problem Statement:**

You have an array $a$ of $n$ integers and an integer $k$. Your task is to find a subset $m$ of a where the following 2 conditions hold:**1)** $prodlimits_{xin m} = 0bmod k$.**2)** Size of $m$ is minimal possible (size of $m gt 0$).

**Constraints:**

$1 le n le 10^4$

$1 le a_i le 10^9$

$2 le k le 10^9$**Time Limit** = 3 seconds**Memory Limit** = 256 MegaBytes

(I am a beginner in the concept of DP, so I am looking for a detailed explanation and if possible. some code. Thanks in advance :D)