Problem name :[VIRATCD]
Author : [Saurabh Mishra]
Tester : [Adarsh Kumar]
Editorialist : [Saurabh Mishra]
Problem difficulty : medium
contest code : ALPH2016
First of all count occurences of a given mumber in the array .
Then count how many number has a multiple of given number in
the array and store that in array count using seive .
Then we just have to count how many numbers have gcd equal to
‘p’ . We can do this by counting pairs with GCD ‘p’ using count
and then excluding pairs which have GCD in multiples of p.
We can easily do this using seive and finally we have a array with
count of GCD[i] denoting pairs with GCD exactly i.
Run a summation from K to 100000 and you have your answer .
Sol link :
 Question cal also be solved by using mobius like done [Here] . : https://www.codechef.com/ALPH2016/problems/VIRATGCD : https://www.codechef.com/users/saurabh_29 : https://www.codechef.com/users/adkroxx : https://www.codechef.com/users/saurabh_29 : https://www.codechef.com/viewsolution/9616597 : https://www.codechef.com/viewsolution/9616586