COPRIME3 - Editorial

general
, , , , ,
1

Problem link : contest practice

Difficulty : Easy-Medium

Pre-requisites : Möbius function, Inclusion-Exclusion Principle

Problem : Given a sequence a1, a2, …, aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1.

Explanation

The problem was estimated to be the third (by the difficulty) in the set.

How to get 22 points

This subtask intends a very trivial solution. It is sufficient just brute-force all the possible triples and to check for every triple that it is a co-prime one. For checking you can use the built-in __gcd() function in C++ and, for example, Euclidean Algorithm in the languages that doesn’t have the built-in GCD function.

There was no intended solution for the second subtask. The purpose of that subtask was to distinguish the people who managed to make some prunings and those who were close to the full-points solution, but forgotten something (for example, long long) from those who did only the brute-force solution.

How to get 100 points

Let’s define the Möbius function μ(X) for the integer X as

  • μ(X) is zero if X is not a square-free integer.
  • μ(X) is 1 if X is a square-free integer and the number of X’s prime divisors is even.
  • μ(X) is -1 if X is a square-free integer and the number of X’s prime divisors is odd.

Then, let’s define the function D(X) for the integer X as

  • D(X) is the number of integers in the given sequence that are divisible by X.

Claim: the solution is sum of μ(X) * C(D(X), 3) over all integer X. Note that if X is greater than the maximal number that occurs in the sequence, then the correspondent term in the sum will be equal to zero, so you can safely consider only the first 106 terms because this is the upper bound on the sequence’s numbers. Here C(N, K) stands for the number of the combinations, basically N!/(K!*(N-K)!). When calculating the solution, you can use the Eratosthenes Sieve for the fast factorization. The values of D(X) can be calculated naively if you will only consider the numbers that are divisible by the corresponding X. Then, the total complexity of this calculation will be [106/1] + [106/2] + [106/3] + … + [106/106] - namely the number of numbers that are divisible by 1 (and less of equal to 106) + the number of numbers that are divisible by 2 (and less of equal to 106) and so on. This number can be estimated as 106 * ln(106).

Now the question is: why is it correct? The correctness of the solution follows from the fact that we can do an inclusion-exclusion principle solution and to show that it is in fact equal to our. That means that we will add to the answer the number of triples that are divisible by some intermediate (in the IEP) product D if D is formed by multiplication of even number of prime numbers and subtract this number of triples otherwise. So, we get:

  • 1 for addition, because that is Möbius function for square-free numbers with even number of prime divisors;
  • -1 for subtraction, that is Möbius function for square-free numbers with odd number of prime divisors;
  • 0 for square-free numbers. By the definition, they can’t occur in out IEP solution.

Related links:

  • More about Möbius function on Wikipedia.
  • The GCD Product problem at HackerRank that also requires you to use the Möbius function.

Solutions : setter tester

21 Likes
2

Nice one…learnt !!! #sabuparseparhogaya

21 Likes
3

Can someone please explain this in setter’s solution:

if (i == 1) dp[i] = 1; else {
			if (p[i / p[i]] == p[i]) dp[i] = 0; else // Checking for non square-free
			dp[i] = -1 * dp[i / p[i]];
		}
		if (!dp[i]) continue;
4

Where can i submit my code for this problem to check if my code is correct?? as there is no submit option for this question ?

5

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

6 Likes
6

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

7

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

2 Likes
8

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
9

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);

}

10

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

1 Like
11

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

12

can anyone please justify the correctness of the method?

13
1 Like
14

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

15

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

16

please help !!!

17

hahaha #SameHere #MathematicalSolution

18

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
19

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

20

One of best explanation ever :ok_hand:

1 Like