Problem link : contest practice
Difficulty : Easy-Medium
Pre-requisites : Möbius function, Inclusion-Exclusion 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.
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^{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!*(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^{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 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.