Hi, I'm having a hard time understanding the author's solution for this problem . I would appreciate it if anyone could explain his/her accepted solution.

Thank you in advance.

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

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

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

1 | 1-gon | 215 |

2 | YouKn0wWho | 190 |

2 | Um_nik | 190 |

4 | sus | 183 |

5 | awoo | 182 |

6 | Errichto | 179 |

7 | tourist | 177 |

8 | -is-this-fft- | 173 |

9 | Radewoosh | 170 |

10 | Ashishgup | 169 |

Hi, I'm having a hard time understanding the author's solution for this problem . I would appreciate it if anyone could explain his/her accepted solution.

Thank you in advance.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2021 03:02:59 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

In order for any 2 numbers a,b to have gcd(a,b) = 1, there should not share any prime factors. So given a number x, we want to count the numbers that are not multiples of any of x's prime factors. This can be done by inclusion and exclusion by first adding all then subtracting the count of each of the primes. Since some numbers can be multiples of several primes, inclusion and exclusion is used. The problem is now reduced to be storing the frequency of all prime combinations. For example, if the added number is 60, 60 = 2*2*3*5, so we add 1 to the entries: f[2], f[3], f[5], f[2*3], f[2*5], f[3*5], f[2*3*5]. To count the number of coprimes of 60, the answer would be M (total count of numbers on shelf)-(f[2]+f[3]+f[5])+(f[2*3]+f[2*5]+f[3*5])-(f[2*3*5]). It is guranteed that the number of operations per query is small since the maximum number of distinct primes for any input number is 6 with 2^6 combinations.

Thank you.