dynamic programming – DP Optimization Problem

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)