COPRIME3 - Editorial

Can someone explain the correctness of this mobius function …im not getting it…

6 Likes

In tester’s solution, I find no use of array (p[]) which is used in the while loop , correct me if I am wrong.

Can’t understand the correctness of mobius function. Pls help!!

2 Likes

the mobius function satisfies the inclusive exclusive property…
refer to Inclusion–exclusion principle - Wikipedia
…we can consider the sets to be numbers. consider the numbers 2,3,4,5,6,10,15,30…4 is a square number . it is totally within 2. so we ignore it. mobius value of square numbers is 0…2,3,5 can be considered as independent sets…intersection of 2 and 3 gives 6…intersection of 3 and 5 gives 15 and of 2 and 5 gives 10…intersection of 2,3,5 gives 30…So, by inclusion - exclusion principle we will multiply numbers with odd number of prime divisors by 1 and even number of prime divisors by -1. so 2,3,5,30 are multiplied by +1 and 6,10,15 by -1 and 4 by 0…hopefully it helps people…

3 Likes

Hello all !!
Can Someone help me in getting what’s wrong with my approach.
Here is my approach
-> with a little knowledge of exclusion/inclusion principle i thought this way !!
-> i factorise the given (1,1000000) using sieve and get all the prime factors corresponding to each A[i] as index.
-> then started from the back I selected every A[i] and go to its prime factorisation array and use inclusion exlusion principle to calculate to all those pairs which gives gcd() > 1 with this . i will show you an example so that you get the whole idea.
->then I find all the divisors of this number i.e A[i] and increment in another array,it is this array which is used to find the number of such pairs which gives with the given element >1

and finally subtract this from the total number of triplets .
i know this approach is little laggy O(n*sqrt(n))
but donot why i am getting WA on some files from each subtask

here is psudo code::

sieve(){
you all know the code
}

main(){

sieve();

int n;

scan(n);

VI arr(n);

int i;

FOR(i,0,n){

scan(arr[i]);

}

brr.resize(MAX);

ll sum=0;

for(i=n-1;i>=0;i–){

int j;

ll ans=0;

int m=P[arr[i]].size();

FOR(j,1,1<<m){

  int k=0;

  int countset=0;

  int temp=j;

  int lcm=1;

  while(temp){

    if(temp&1){

     lcm=lcm*P[arr[i]][k];

     countset++;

    }

    temp/=2;

    k++;

  }

  ll sz=brr[lcm];

  if(countset&1){

    ans+=((sz*(sz-1))/2);


  }else{

    ans-=((sz*(sz-1))/2);

  }

}

sum+=ans;

int sqrtt=sqrt(arr[i]);

FOR(j,1,sqrtt+1){

 if(arr[i]%j==0){

   brr[j]++;


   if((arr[i]/j)!=j){

     brr[arr[i]/j]++;


   }

  }

}

}

ll pairs=((ll)n*(ll)(n-1)*(ll)(n-2))/6;

printll(pairs-sum);

}

What The Hell was That O_O Can Someone Please Explain me The Mobius Function in an Easy Way !!! #PuraBCBouncer

1 Like

Here is a short description of how to calculate Mobius Function,U(x)

Approach is similar to Sieve of Erathosthenes

from setters solution :

// This is simple sieve of eratosthenes where each number is marked with its smallest prime factor.
for(int i=2;i<=maxi;i++){
		int j = i;
		if(!p[i])
		while(j<=maxi){
			if(!p[j])
				p[j] = i;
			j += i;
		}
	}
// calculation of Mobius function
for(int i=1;i<=maxi;i++){
	if(i == 1){
		dp[i] = 1; trivial case , U(1) = 1
	}
	else{   
            // checks if number is square free or not 
            // suppose if i == 9,then p[9] = 3,p[3] = 3
            // p[9/p[3]] = p[3] hence it's not square free.
            if(p[i/p[i]] == p[i]) 
	        dp[i] = 0; // not square free
	    else{
                // it puts dp[i] = 1 if it has even numbers of prime factors else -1 for odd number of prime factors.
	        dp[i] = -1 * dp[i/p[i]]; 
	    }
	}

For sieve of eratosthenes you can refer [link1][1]
[1]: Sieve of Eratosthenes - Wikipedia

can anyone please justify the correctness of the method?

1 Like

is there no other way to find it it seems quite tough…

yes there is an easier way refer to uwi’s solution
http://www.codechef.com/viewsolution/4153324

please help !!!

hahaha #SameHere #MathematicalSolution

Ill try my best here to explain the Inclusion and Exclusion part. Hopefully this should give you some intuition.

So lets say we have a sequence of numbers 1, 2, 3, … 29, 30 and we want to find all pairs that have GCD = 1.

1 says all possible pairs (1, 2) (1, 3) … (2, 4) … (3, 6) … (29, 30) here have a GCD of 1. (Notice here that some pairs don’t actually have GCD of 1 we will exclude the ones that dont have GCD=1 in later steps)

2 comes along and tells 1, you cannot include pairs like (2,4) (2, 6) … (4, 8) … (6, 12) … (28, 30) because they have a GCD of 2 (Notice here that some pairs don’t actually have GCD of 2 we will exclude the ones that dont have GCD=2 in later steps). So now we subtract all these pairs. These are basically all multiples of 2 between 1 and 30.

3 also comes along and tells 1, you cannot include pairs like (3, 6) (6, 9) … (6, 12) … (9, 18) … (27, 30) because they have a GCD of 3. So 3 removes all these pairs.

4 now realizes that it does not need to remove the pairs from what 1 has claimed because 2 already removed it for him. Pairs such as (4, 8), (8, 12) were already excluded by 2.

5 Five also removes all its pair from what 1 has claimed.

6 now has an interesting decision to make. 2 excluded multiples of 6 and removed them. 3 also excluded multiples of 6 and removed them. So now 6 says, I have been removed twice by 2 and 3, so I must include all my pairs again. So he includes pairs like (6, 12) (6, 18) … (12, 18) … (24, 30) to balance the double subtraction by 2 and 3

… this goes on until each number has decided to either exclude/include its multiples.

Do you see the pattern here? If you notice this directly corresponds to the Mobius values

\mu (1) = +1 \space (Include)
\mu (2) = -1 \space (Exclude)
\mu (3) = -1 \space (Exclude)
\mu (4) = \space \space \space 0 \space (Do \space Nothing)
\mu (5) = -1 \space (Exclude)
\mu (6) = +1 \space (Include)

Hope this helped build an intuition. For why we subtract if a number has odd prime factors and why we add if a number has even prime factors.

33 Likes

How can we precompute mobius function values ? could you please explain possibly with a psuedo code?

One of best explanation ever :ok_hand:

1 Like

Nice problem, learnt something new.

1 Like

I am trying to explain it in lengthy way but this is very very very helpful and easy to understand.

Before explaining solution I want to make you understand something that will be very helpful for this problem. You will think why I am explaining very easy concepts, there is only one reason — I want to make my editorial understand for everyone. Everyone means everyone — who are new to the programming.

  1. What is GCD?

Full form for GCD is Greatest Common Divisor. Let’s understand this concept by taking an example.

Let say a = 10, b = 20. What is the GCD of a, b?

Divisors for “a” are [1,2,5,10] and Divisors for “b” are [1,2,4,5,10,20]. What is the greatest common divisor between these two — “10”. So the answer is 10. This is very basic concept.

  1. What are co-prime numbers?

Definition: Two numbers are co-prime if GCD of those two numbers are 1 .

Let’s understand this concept by taking an example.

Let say a = 5, b = 7. These two numbers are co-prime or not? Divisors for “a” are [1,5] and Divisors for “b” are [1,7]. So GCD(a, b) = 1 . So, these two numbers are co-prime.

Let say a = 5, b = 10. These two numbers are co-prime or not? Divisors for “a” are [1,5] and Divisors for “b” are [1,5,10]. So GCD(a, b) = 5 . So, these two numbers are not co-prime.

Now let’s jump to our main problem.

Problem Statement: Given a sequence [A1, A2, …, AN]. Count number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(Ai, Aj, Ak) = 1.

So in brief, we have to find number of co-prime triples in an array.

Now, what is the first thing in your mind when you want to solve this problem? I think check for every number in array, check whether triple have GCD 1, if GCD is 1 for triple then increment count. Repeat this process until last element of array and print count.

Yes this is nice approach, But I have better approach for this problem than this. Now let’s understand better approach by taking an example. First we will find number of pairs with 2 elements which are co-prime. Don’t forget this. :slight_smile:

arr = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

Now we will write multiples of each number till last element and also count how many multiples are there for each multiple in array.

multiples of 1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] (20)

multiples of 2 = [2,4,6,8,10,12,14,16,18,20] (10)

multiples of 3 = [3,6,9,12,15,18] (6)

multiples of 4 = [4,8,12,16,20] (5)

multiples of 5 = [5,10,15,20] (4)

multiples of 6 = [6,12,18] (3)

multiples of 7 = [7,14] (2)

multiples of 8 = [8,16] (2)

multiples of 9 = [9,18] (2)

multiples of 10 = [10,20] (2)

multiple of 11 = [11] (1)

multiple of 12 = [12] (1)

multiple of 13 = [13] (1)

multiple of 14 = [14] (1)

multiple of 15 = [15] (1)

multiple of 16 = [16] (1)

multiple of 17 = [17] (1)

multiple of 18 = [18] (1)

multiple of 19 = [19] (1)

multiple of 20= [20] (1)

Do you understand the concept? If not then it’s fine, if yes then it’s very fine. I am here for you.

Here what is the meaning of Multiples of 1?

  • This will give you list of numbers whose GCD = multiple of 1 for any pair of two numbers in list.

Let’s understand above statement by one of the multiple.

multiples of 2 = [2,4,6,8,10,12,14,16,18,20] (10)

Here count is 10 for array for number of multiples of 2. This is the list of numbers whose GCD = multiple of 2 for any pair of two numbers in the list.

Here you can see that GCD for all pairs is multiple of 2, because they are multiple for 2. This statement is true for all multiples(1 to 20) that we have defined above.

Now my question is how to find count of number of pairs which have GCD 2. Here from above table we can count that number of pairs are 45 . Yes, that is the count. Now next thing is how to find this count.

As we have 10 multiples of number 2. Here all numbers are multiple of 2. In how many ways we can select/choose 2 elements from these 10 elements? I think you have got me. In other words how many combinations of 2 elements to choose if we have 10 elements. This is combination thing. You can find this by (nCr) formula.

Here n = 10, r = 2. So, 10C2 = (10!)/((10–2)!*(2!)) = 45. Here is the link if you want to understand combination thing in deep. Mathwords: Combination Formula

Let’s make out formula for Nc2. (N!)/((N-2)!2!) → (N(N-1)*(N-2)!)/((N-2)!2!) → (N(N-1))/2.

Now we will calculate this for every count, so here we are counting number of pairs with GCD of multiple of “x”.

image

Have you got now what I am trying to say? If yes then It is very good, if no then also it’s fine because I am here for you.

Now it is the table for number of pairs with GCD = multiple of each element of array . Now Let me tell you one fact from this table. Let say we want to find number of pairs with GCD = EXACTLY 2 . How can we find this from table? Here Number 2 contains number of pairs with GCD of multiple of 2. Let me tell you in another words, number 2(2nd row) contains number of pairs with GCD = 2,4,6,8,10,12,14,16,18,20). How can we find GCD = exactly 2. Simple,

We need to remove number of pairs with GCD = exactly 4,6,8,10,12,14,16,18,20. Here we will go backwards. Because we have to find number of pairs with exactly array element. So number of pairs with GCD exactly 20 = (number of pairs with GCD exactly 20-number of pairs with GCD exactly 40 etc.) = 0

GCD exactly 19 = (number of pairs with GCD exactly 19-number of pairs with GCD exactly 38 etc.) = 0

And so on. Now If we don’t go backwards then we will subtract GCD multiple of array element. Here we are finding pairs with exact GCD.

Multiple of 2 except 2. So, GCD = exactly 2 → 45(GCD of multiple of 2)-9(GCD exactly 4)-3(GCD exactly 6)-1(GCD exactly 8)-1(GCD exactly 10)-0(GCD exactly 12)-0(GCD exactly 14)-0(GCD exactly 16)-0(GCD exactly 18)-0(GCD exactly 20)=31. There are 31 pairs which have GCD exactly 2.

Why are we removing this?

Here 2 will contain number of pairs with GCD 2,4,6,8,10,12,14,16,18,20.

3 will contain number of pairs with GCD 3,6,9,12,15,18.

4 will contain number of pairs with GCD 4,8,12,16,20.

So we are removing other pairs for each array element except current element.

So, from this table we can say that in our example number of pairs(2 elements) with GCD = 1(co-prime) are 127 .

Now focus to our main problem, where we have to find number of triplets with GCD = 1(co-prime). Only one thing will change here. Instead of nC2, we will take nC3. Because we have to select/choose 3 elements from these 10 elements?

Here is the formula.

Formula for nC3

Here is the table for co-prime triples.

So, answer here for number of pairs with GCD exactly 1 is 997 .

Here is the solution link for the problem.

CodeChef: Practical coding for everyone.

If you find this editorial helpful, please give heart for it as I have put so much hard work for it.

Thank you.

26 Likes

Thanks for the explanation. : - )

1 Like

kudos explanation … bro you are awesome .

1 Like