Count special subsets
/

Dynamic programming, Factorization, Mathematics, 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.hackerearth.com/problem/algorithm/distinct-distinct-a31c41ec/", "fetch_time": 1591399229000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2020-24/segments/1590348504341.78/warc/CC-MAIN-20200605205507-20200605235507-00577.warc.gz", "warc_record_offset": 750740695, "warc_record_length": 25807, "token_count": 521, "char_count": 1741, "score": 3.953125, "int_score": 4, "crawl": "CC-MAIN-2020-24", "snapshot_type": "latest", "language": "en", "language_score": 0.7244275212287903, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00044-of-00064.parquet"}