How inclusion exclusion is related with Mobius function ? In F.Relatively Prime Powers judge solution with Mobius function.

Can anyone help me get the trick for this problem with Mobius function ?

# | User | Rating |
---|---|---|

1 | tourist | 3372 |

2 | mnbvmar | 3345 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | Radewoosh | 3230 |

5 | scott_wu | 3189 |

6 | Benq | 3187 |

7 | LHiC | 3171 |

8 | Um_nik | 3155 |

9 | V--o_o--V | 3152 |

10 | Petr | 3139 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 172 |

3 | rng_58 | 158 |

4 | neal | 156 |

5 | Um_nik | 154 |

5 | tourist | 154 |

7 | Petr | 152 |

7 | Ashishgup | 152 |

9 | 300iq | 150 |

9 | PikMike | 150 |

How inclusion exclusion is related with Mobius function ? In F.Relatively Prime Powers judge solution with Mobius function.

Can anyone help me get the trick for this problem with Mobius function ?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/19/2018 09:20:49 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

In this problem, we know how to count the number of integers from 2 to

nhavinggcdofk_{i}divisible by some numberx(that is just , since we have exactly this number of integers not less than 2 that can be raised tox-th power without exceedingn), but we need to count the number of integers having thisgcdexactly equal to 1.How would we handle this with usual inclusion-exclusion? Let

Sbe some set of prime numbers, andf(S) be the product of primes fromS(ifSis empty, thenf(S) = 1), then the answer would be by inclusion-exclusion formula. Note that in previous formula we are summing up these values over all possible sets of prime numbersS— and since we have infinitely many prime numbers, the number of possible setsSis also infinite.However, we know that for sufficiently large

x(in the case of this problem, for something likex> 60, but typically we can apply this technique even if the border is somewhere at 10^{6}) the number of integers such thatgcdof theirk_{i}is divisible byxbecomes 0 (because quickly becomes equal to 1). And that is what gives us an opportunity to apply Mobius function.In the formula listed above, we iterated over sets of primes. Let's have it backwards: we will iterate on the integer

x, and for each such integer try to count the number of sets havingf(S) =x, and the number of primes in these sets.If the factorization of

xcontains some prime number twice (or even more than twice), then there is no such set of prime numbersSsuch thatf(S) =x. Otherwise, there is exactly one such setSwhich is equal to the factorization ofx; and if the factorization contains even number of primes, then ( - 1)^{|S|}= 1, otherwise ( - 1)^{|S|}= - 1.And now we can actually see that the previous two sentences are actually very close to the definition of Mobius function! If the factorization of

xcontains some prime twice or more, then μ (x) = 0, otherwise if the number of primes in the factorization ofxis odd, then μ (x) = - 1, and if it is even, then μ (x) = 1. This actually allows us to rewrite the formula in a more calculatable way: , whereMis some constant after which all the summands become equal to 0 (in this problemMis somewhere close to 60).If there are some questions, I can try to elaborate a bit more. In fact, we gave some other problems using this technique on previous Educational Rounds, so you can try solving them to understand it better: 915G 803F 920G

Thank u sir.Finally got it.Now I can die in peace.

BledDest Thanks for explanation.

I don't understand why that summation over all possible sets of prime numbers gives us what we want.

Actually i have two problems here:

why summing over sets of prime numbers?

Assuming first problem is solved, why does this summation gives us total number of numbers with power's gcd of one? i mean why one?

What would i get by doing as you explained if i define S over just some limited selected primes like {2, 3, 11}?