Editorial - VIRAT AND GCD

general
, , ,
1

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
2

Can someone please explain the mobius solution

    // 1
    for(i=k;i<=upperlimit;i++)
        f[i]=1;

    // 2
    for(i=1;i<=upperlimit;i++){
        if(mobius[i]){
            for(j=i;j<=upperlimit;j+=i){
                h[j]+=mobius[i]*f[j/i];
            }
        }
    }

  1. what is f[] storing

  2. how is the h[] calculated

I have read about the mobius function but not able to figure out the solution. Can some explain the formula
@liouzhou_101 @meooow @likecs

1 Like
3

f[i] is just the boolean function [i >= k].
h[i] is \sum_{d \mid i} \mu(d) [i/d >= k] = \sum_{d \mid i} \mu(\frac{i}{d}) \left[d >= k \right].

I’m still figuring out the working, but example 1 and 2 of this article have been very helpful.

4

thanks for that article