TCS mockvita 2018

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.

2 Likes

See my solution over here.

I just simply count all the elements whose factors are, P \cdot Q, \ P, \ Q. After that I just count all the subsets that can be formed by combining all of them.

2 Likes

thanks a lot :)…

dp[i][rem]. Where you already consider first i numbers, current remainder by modulo p × q = rem. dp[i][rem] = number of ways to obtaine this configuration. The transitions can be done in p × q, which will produce in final O(npq)

https://pastebin.com/GqjtfQsi

1 Like

@bansal1232 can you explain this line in your code
ans = (ans%mod + (power(2,both, mod) - 1) * power(2,rem+y+x, mod)) % mod;
Thanks.

can someone tell the math behind this?