All Tracks Math Number Theory Problem

Count special subsets
Tag(s):

Dynamic programming, Integer Factorization, Math, Medium, Number Theory

Problem
Editorial
Analytics

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

 

SAMPLE INPUT
1
5 10
5 9 16 20 25
SAMPLE OUTPUT
11
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #6

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?