Problem link : contest practice Difficulty : EasyMedium Prerequisites : Möbius function, InclusionExclusion Principle Problem : Given a sequence a_{1}, a_{2}, ..., 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. ExplanationThe problem was estimated to be the third (by the difficulty) in the set. How to get 22 pointsThis subtask intends a very trivial solution. It is sufficient just bruteforce all the possible triples and to check for every triple that it is a coprime one. For checking you can use the builtin __gcd() function in C++ and, for example, Euclidean Algorithm in the languages that doesn't have the builtin 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 fullpoints solution, but forgotten something (for example, long long) from those who did only the bruteforce solution. How to get 100 pointsLet's define the Möbius function μ(X) for the integer X as
Then, let's define the function D(X) for the integer X as
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^{6} 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!*(NK)!). 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^{6}/1] + [10^{6}/2] + [10^{6}/3] + … + [10^{6}/10^{6}]  namely the number of numbers that are divisible by 1 (and less of equal to 10^{6}) + the number of numbers that are divisible by 2 (and less of equal to 10^{6}) and so on. This number can be estimated as 10^{6} * ln(10^{6}). Now the question is: why is it correct? The correctness of the solution follows from the fact that we can do an inclusionexclusion 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:
Related links:
This question is marked "community wiki".
asked 29 Jun '14, 14:01

Nice one...learnt !!! #sabuparseparhogaya answered 29 Jun '14, 14:31

Can someone explain the correctness of this mobius function ....im not getting it... answered 29 Jun '14, 18:02

Can't understand the correctness of mobius function. Pls help!! answered 30 Jun '14, 00:07

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... answered 30 Jun '14, 00:39

Can someone please explain this in setter's solution:
answered 29 Jun '14, 16:35

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

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=n1;i>=0;i){
} ll pairs=((ll)n(ll)(n1)(ll)(n2))/6; printll(pairssum); } answered 30 Jun '14, 00:43

What The Hell was That O_O Can Someone Please Explain me The Mobius Function in an Easy Way !!! #PuraBCBouncer answered 28 Sep '14, 10:00

Here is a short description of how to calculate Mobius Function,U(x) // 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{For sieve of eratosthenes you can refer link1 answered 01 Sep '16, 11:45

can anyone please justify the correctness of the method?
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