Hey guys,
There was a question asked in tcs mockvita 2018,the problem statement is described below.It would be of great help if anyone could suggest some ideas or solution for this problem.Thanks in advance.
Problem Statement:
You are given a set of N positive integers and two small prime numbers P and Q (not necessarily distinct). You need to write a program to count the number of subsets of the set of N numbers whose product is divisible by PQ (the product of P and Q). Since the number K of such sets can be huge, output K modulo 1009 (the remainder when K is divided by 1009).
Constraints
N <= 300
P,Q <=50
The integers are <= 10000
Input Format
First line three comma separated integers N, P,Q
The next line contains N comma separated integers
Output
One integer giving the number of subsets the product of whose elements is divisible by PQ. Give the result modulo 1009.
Example 1
Input
4,5,7
5,49,10,27
Output
6
Explanation
N is 4, P is 5, Q is 7. We need to find subsets of the numbers given so that the product of the elements is divisible by 35 (the product of 5 and 7). These subsets are (5,49),(5,49,10),(5,49,27),(5,49,10,27), (49,10),(49,10,27). There are 6 subsets, and the output is 6.
Example 2
Input
4,11,13
3,7,12,13
Output
0
Explanation
N is 4, P is 11, Q is 13. We need to find subsets of the numbers given so that the product of the elements is divisible by 143 (the product of 11 and 13).As none of the N numbers is divisible by 11 (a prime number), there are no subsets for which the product of the elements is divisible by 143. Hence the output is 0.