|
||||||||||
I love triplesTime Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 581 Accepted Submission(s): 135 Problem Description Now Mr.I has an array $a$ consisting of $n$ integers. He now wants to know how many triples $(i, j, k)$ satisfy $i<j<k$ and $a_i * a_j * a_k$ is a square number . The definition of a square number is a number that can be expressed as the product of two identical integers. For example, 1, 4, 9, 16, 25, and 36 are square numbers, but 2, 3, and 6 are not. Input The first line contains an integer $T(T\leq 6)$ . Then $T$ test cases follow. Each test case contains two lines. The first one contains an integer $n(1\leq n\leq {10}^5)$ — length of the array $a$. The second one contains $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq {10}^5)$ Output For each test case, output a single line containing a single integer — the number of triples that meet the conditions. Sample Input
Sample Output
Source | ||||||||||
|