COPRIME3 - Editorial

[xcwgf666]

Problem link : contest practice

Difficulty : Easy-Medium

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

Problem : Given a sequence a₁, a₂, …, a_N. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(a_i, a_j, a_k) = 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 10⁶ 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 [10⁶/1] + [10⁶/2] + [10⁶/3] + … + [10⁶/10⁶] - namely the number of numbers that are divisible by 1 (and less of equal to 10⁶) + the number of numbers that are divisible by 2 (and less of equal to 10⁶) and so on. This number can be estimated as 10⁶ * ln(10⁶).

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

[wonder]

Nice one…learnt !!! #sabuparseparhogaya

[thefighter]

can anyone please justify the correctness of the method?

[damn_me]

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;

[grvnr1995]

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 ?

[damn_me]

Coprime Triples | CodeChef

[subhamlfc]

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

[nivin]

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

[wonder]

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

[siddhartha4444]

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

[black_grape]

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

[subhamlfc]

the mobius function satisfies the inclusive exclusive property…
refer to http://en.wikipedia.org/wiki/Inclusion–exclusion_principle
…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…

[kodoos]

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

}

[kodoos]

please help !!!

[siddharths067]

hahaha #SameHere #MathematicalSolution

[siddharths067]

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

[alphaguy]

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]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes