# 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)