Can somebody provide the editorial for this question → AMCOP Problem - CodeChef
And please explain me mobius function calculation that you use in this function?
It can be done with inclusion exclusion. Mobius function is only there for convenience.
When the GCD to be 1, for each prime p there must exist a number in the set that does not divide p.
Let’s start by calculating the number of sets. It’s just \binom{n}{k}. To find the number of sets whose GCD is multiple of p, we can just count the number of elements divisible by p. Let’s denote that F_p. So the number of sets such that p divides their GCD is \binom{F_p}{k}.
Let P denote the set of all primes. We can do \binom{n}{k} - \sum_{p\in P} \binom{F_p}{k} Now we are removing the GCDs with multiple prime factors many times. To fix that we can use inclusion exclusion. We just need to add the ones that divide 2 prime factors, and subtract the ones with 3 prime factors and so on.
So something like
\binom{n}{k} - \sum_{p\in P}\binom{F_p}{k} + \sum_{(p,q) \in P} \binom{F_{pq}}{k} - \sum_{(p,q,r) \in P} \binom{F_{pqr}}{k} \dots
p\not =q\not=r.
You can notice that none of these numbers can ever divide a square. You can also notice that we add the ones with even number of prime factors, and subtract the ones with odd number of prime factors. So let’s create a new function, \mu(x), that is 0 if x is divisible by some square, -1 if it is divisible by an odd number of primes, and 1 if it is divisible by an even number of primes. So now we can just do \sum\mu(x)\binom{F_x}{k}. Notice that \mu(1) is 1 and F_1 = n.
We can notice that F_x is 0 for all x>max(A). So we can ignore them. Let’s say we want to add a number. A number less that 10^5 may not contain more than 6 different primes, therefore can change F_x for at most 2^6 relevant values(For all x that are not divisible by a square).
I hope you can extend it from here.
4 Likes
Thanks a lot it really helped my understanding regarding mobius function.