[Solution] Square Function solution codechef

Square Function solution codechef

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

F(X)=XYF(X)=XY

where YY is the largest perfect square that divides XX.

For example,

• The largest perfect square that divides 1212 is 44. Hence F(12)=124=3F(12)=124=3.
• The largest perfect square that divides 3636 is 3636. Hence F(36)=3636=1F(36)=3636=1.
• The largest perfect square that divides 77 is 11. Hence F(7)=71=7F(7)=71=7.

You are given an array AA consisting of NN integers. A pair of integer (iijj) is called Good if 1i<jN1≤i<j≤N and F(AiAj)>1F(Ai∗Aj)>1. Find the number of Good pairs.

Input Format Square Function solution codechef

• The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains an integer NN.
• The second line of each testcase contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format Square Function solution codechef

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

Constraints Square Function solution codechef

• 1T1041≤T≤104
• 1N1051≤N≤105
• 1Ai1061≤Ai≤106
• The sum of NN over all test cases does not exceed 106106.

3
3
2 3 12
4
1 2 3 4
3
2 3 7

2
5
3

Explanation

Test case 11:

• (i=1,j=2)(i=1,j=2)F(A1A2)=F(23)=F(6)=61=6>1F(A1∗A2)=F(2∗3)=F(6)=61=6>1.

• (i=1,j=3)(i=1,j=3)F(A1A3)=F(212)=F(24)=244=6>1F(A1∗A3)=F(2∗12)=F(24)=244=6>1.

• (i=2,j=3)(i=2,j=3)F(A2A3)=F(312)=F(36)=3636=11F(A2∗A3)=F(3∗12)=F(36)=3636=1≯1.

So there are 2 Good pairs.

Test case 22: All pairs except (1,41,4) are Good pairs as F(A1A4)=F(14)=F(4)=44=11F(A1∗A4)=F(1∗4)=F(4)=44=1≯1.

Test case 33: All pairs are Good pairs.