You are given N integers. Each integer is square free (i.e. it has no divisor which is a square number except 1) and all the prime factors are less than 50. You have to find out the number of pairs are there such that their GCD is 1 or a prime number. Note that (i,j) and (j,i) are different pairs if i and j are different.
The first line contains an integer T(1 <= T <= 10), the number of tests. Then T tests follows. First line of each tests contain an integer N (1 <= N <= 100000). The next line follows N integers.
Print T lines. In each line print the required result.
1 3 2 1 6
gcd(1,2) = 1 gcd(2,1) = 1 gcd(2,6) = 2, a prime number gcd(6,2) = 2, a prime number gcd(1,6) = 1 gcd(6,1) = 1 gcd(2,2) = 2, a prime number gcd(1,1) = 1
This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.
nfssdqNafis was a student of Jahangirnagar University, a die-hard programming contestant. His team became the champion in ACM-ICPC Dhaka Regional 2015. He participated in the 39th and 40th ACM-ICPC World Finals. →