You are not logged in. Please login at www.codechef.com to post your questions!

×

COPRIME3 - Editorial

18
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

This question is marked "community wiki".

asked 29 Jun '14, 14:01

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719426277
accept rate: 0%

edited 16 Jun '15, 11:38

vicky002's gravatar image

1★vicky002 ♦♦
2561312

can anyone please justify the correctness of the method?

(29 Jun '14, 15:45) thefighter2★

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

(29 Jun '14, 19:09) wonder2★

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

(30 Jun '14, 00:01) siddhartha44443★

12

Nice one...learnt !!! #sabuparseparhogaya

link

answered 29 Jun '14, 14:31

wonder's gravatar image

2★wonder
351183769
accept rate: 0%

edited 29 Jun '14, 18:35

hahaha #SameHere #MathematicalSolution

(28 Sep '14, 09:55) siddharths0671★

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

link

answered 29 Jun '14, 18:02

subhamlfc's gravatar image

5★subhamlfc
10626
accept rate: 0%

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

link

answered 30 Jun '14, 00:07

black_grape's gravatar image

4★black_grape
46114
accept rate: 0%

the mobius function satisfies the inclusive exclusive property... refer to http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_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...

link

answered 30 Jun '14, 00:39

subhamlfc's gravatar image

5★subhamlfc
10626
accept rate: 0%

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

answered 29 Jun '14, 16:35

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

edited 29 Jun '14, 16:51

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 ?

link

answered 29 Jun '14, 17:36

grvnr1995's gravatar image

3★grvnr1995
1
accept rate: 0%

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

link

answered 29 Jun '14, 18:25

nivin's gravatar image

3★nivin
112
accept rate: 0%

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

}

link

answered 30 Jun '14, 00:43

kodoos's gravatar image

4★kodoos
11
accept rate: 0%

please help !!!

(30 Jun '14, 00:43) kodoos4★

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

link

answered 28 Sep '14, 10:00

siddharths067's gravatar image

1★siddharths067
7916
accept rate: 4%

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

link

answered 01 Sep '16, 11:45

alphaguy's gravatar image

3★alphaguy
161
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,081
×213
×186
×64
×13
×6

question asked: 29 Jun '14, 14:01

question was seen: 11,117 times

last updated: 01 Sep '16, 11:45