I tried to solve this problem with the help of bitmask. Because the number of prime is very low. But couldn't come up with a exact solution. It will be helpful if anyone help me to find out a solution. The problem statement is given below:
You are given N(1<=N<=100000) integers. Each integer is square free(meaning 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.
Input:
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. The next line follows N integers.
Output:
Print T lines. In each line print the required result.
Sample Input:
1
3
2 1 6
Sample Output
8
Well, I'm not really sure about this, and there may be solution simpler, but following seems legit.
Let's make an observation that number is square free only when all its prime factors have power of 1. Now we should transorm every number in our array to bitmask, in which the i-th bit is 1 when i-th prime is in prime factoriastion of that number. We can do it just by trying dividing a number by primes from 2 to 47. Also we need to count occurences of each bitmask — let map[b] be the number of occurences of bitmask b in our array.
After that we should make another observation: in constraints of this problem two numbers have prime or 1 gcd only when AND of their bitmasks (like described higher) is 0 (meaning they have no common prime factors) or power of 2 (meaning they have 1 common prime factor).
Now we can make it to the solution itself. For each bitmask in our transformed array let's flip all it's bits, look in map for amount of occurences of inverted bitmask and add it to answer. After that for every bit of inverted bitmask let's try to flip it back and add to the answer amount of occurences of gotten bitmask.
Total complexity is O(N*15) (15 is amount of primes from 2 to 47) for one test case.
I would be glad to hear simpler solution or criticism of my solution.
And sorry for bad English.
Since there can be bits which are missing in a pair of number (e.g. prime 2 is missing in both 3 and 5), finding amount of occurences of inverted bitmask will miss some of the gcd pairs, so this part needs some more care.
Yes, just woke up and understood it myself. Solving problems at 3 am wasn't a good idea :D
Actually I thought the same procedure. But how can i get the AND of the masks are 0 or power of 2, as there can be 2^15 mask value. I am not clear about this
Here's AC code http://ideone.com/Ed7eCW
What is the complexity?
For each mask, say X = the number obtained by flipping all bits of this mask. Denote sol, the count for the current mask. sol = 0 initially. For each submask of X: 1. add to sol ap[submask](pairs with gcd 1). 2. add to sol numbers of form ap[submask | (1 << i)], where number i is some bit set to 1 in normal mask.(those are pairs with prime gcd)
Now go through all distinct masks that appeared in input, compute sol[mask] and add sol[mask] * ap[mask] to solution.
Is it to possible to repeat pairs? e.g:
4
1 2 1 2
Should we count both (1, 2) (first and second numbers) and (1, 2) (third and fourth numbers)?
Yes, problem statement says : "Note that (i,j) and (j,i) are different pairs if i and j are different."