All Tracks Math Number Theory Problem

Count special subsets

Dynamic programming, Factorization, Mathematics, Number Theory


You are given an array \(a\) of \(n\) integers and another integer \(x\). You need to determine the number of special subsets of those \(n\) integers. If a subset is not empty and the resultant score of that subset is equal to \(x\), then that subset is called a special subset

Consider a number \(s\) that is equal to the product of all the integers in a subset. The resultant score of that subset is the product of all the distinct prime numbers that divide the number \(s\).

For example, let us consider that \(a = [5, 9, 16, 20, 25]\) and \(x = 10\). Consider the subset \([5, 16, 20]\). The product of all the integers in this subset is \(s = 1600\). The prime numbers that divide this number \(s\) are \(2\) and \(5\). So the resultant score of this subset is \(2*5 = 10\). As this score is equal to \(x\) ,therefore, the selected subset is considered as a special subset.

Input format

  • First line: A single integer \(t\) that denotes the number of test cases
  • For each test case:
    • First line: Two integers \(n\) and \(x\) 
    • Next line: \(n\) space-separated integers of the array \(a\)

Output format

For each test case, print a single integer representing the number of special subsets of the given array. Since the answer can be very large, print it modulo \(10^9+7\).

Input Constraints

  • \(1 \le t \le 5\)
  • \(1 \le n \le 50000\)
  • \(1 \le a_i \le 10^6\)
  • \(2 \le x \le 10^6\)


5 10
5 9 16 20 25

In the sample test case, here's a list of some of the special subsets: \([5, 16], [20], [5, 20], [16, 20]\) and \([5, 16, 20]\).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications