**Problem name** :[VIRATCD][1]

**Author** : [Saurabh Mishra][2]

**Tester** : [Adarsh Kumar][3]

**Editorialist** : [Saurabh Mishra][4]

**Problem difficulty** : medium

**contest code** : ALPH2016

**Prerequiste** :Seive

**Editorial** :

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 .

Tada .

Sol link :

```
[5]
Question cal also be solved by using mobius like done [Here][6] .
[1]: https://www.codechef.com/ALPH2016/problems/VIRATGCD
[2]: https://www.codechef.com/users/saurabh_29
[3]: https://www.codechef.com/users/adkroxx
[4]: https://www.codechef.com/users/saurabh_29
[5]: https://www.codechef.com/viewsolution/9616597
[6]: https://www.codechef.com/viewsolution/9616586
```