Square Function solution codechef

For Solution

Click Here!

Let’s define a function $F (X)$ as follows:

F (X) = X Y

where $Y$ is the largest perfect square that divides $X$ .

For example,

The largest perfect square that divides $12$ is $4$ . Hence $F (12) = \frac{12}{4} = 3$ .
The largest perfect square that divides $36$ is $36$ . Hence $F (36) = \frac{36}{36} = 1$ .
The largest perfect square that divides $7$ is $1$ . Hence $F (7) = \frac{7}{1} = 7$ .

You are given an array $A$ consisting of $N$ integers. A pair of integer ( $i$ , $j$ ) is called Good if $1 \leq i < j \leq N$ and $F (A_{i} * A_{j}) > 1$ . Find the number of Good pairs. Square Function solution codechef

Input Format

The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains an integer $N$ .
The second line of each testcase contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format Square Function solution codechef

For each test case, print a single line containing one integer – the number of Good pairs.

Constraints

$1 \leq T \leq 10^{4}$
$1 \leq N \leq 10^{5}$
$1 \leq A_{i} \leq 10^{6}$
The sum of $N$ over all test cases does not exceed $10^{6}$ .

Sample Input 1 Square Function solution codechef

Sample Output 1

2
5
3

Explanation

Test case $1$ :

$(i = 1, j = 2)$ : $F (A_{1} * A_{2}) = F (2 * 3) = F (6) = \frac{6}{1} = 6 > 1$ .
$(i = 1, j = 3)$ : $F (A_{1} * A_{3}) = F (2 * 12) = F (24) = \frac{24}{4} = 6 > 1$ .
$(i = 2, j = 3)$ : $F (A_{2} * A_{3}) = F (3 * 12) = F (36) = \frac{36}{36} = 1 ≯ 1$ .

So there are 2 Good pairs.

Test case $2$ : All pairs except ( $1, 4$ ) are Good pairs as $F (A_{1} * A_{4}) = F (1 * 4) = F (4) = \frac{4}{4} = 1 ≯ 1$ .

Test case $3$ : All pairs are Good pairs.

For Solution

Click Here!