PROBLEM LINK:
CNTSET - A Gift from Rick IUPC-Plinth’20
Author - priyam2k
Editorialist - Priyam Khandelwal
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, GCD, Factorization
PROBLEM:
Given a number K and an array A. Find number of subsets (modulo prime) whose multiplication of elements is divisible by K.
Explanation
There are two approaches that I know of, I’ll try to explain both of them a little.
1.) We will iterate the array, for every element we will have two options either to take it into current subset or ignore it for current subset. If we take it into our set, notice how gcd of subset will change gcd_{new} = GCD(gcd_{before}*a[i],k). Using this we can count how many subsets have their GCD \geq K.
2.) Second Approach is use DP over prime factors. We can make a vector of pairs which will denote the distinct prime factors and their powers in the given K. After that we iterate the array and again for element we have two choices either we take it into current subset or leave it. If we take it we will update our vector which stores prime factors and their powers of the current subset. Then all that is left is to match all prime factors whether they have the required power.
The first approach is quite easy to implement compared to the second.