Problem Name: Ray Gun

Problem Link: http://lightoj.com:81/volume/problem/1144

Any hints for the solution will be really appreciated.

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

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

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

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 185 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 176 |

10 | -is-this-fft- | 171 |

Problem Name: Ray Gun

Problem Link: http://lightoj.com:81/volume/problem/1144

Any hints for the solution will be really appreciated.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/25/2021 16:42:34 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

There are many observations to make in order to get to a working solution.

i,j), the ray that intersects it is unique and it's identified by the pair , wheregis thegcdofiandj.a≤Nandb≤M. This is the same as counting for everyibetween 1 andN, the amount of numbers in the range [1,M] that are coprime withi.xwith prime factorsp_{1},p_{2}. How do we know how many numbers in range [1,M] are coprime with it? That's equal to M minus the amount of multiples ofp_{1}minus the amount of multiples ofp_{2}plus the amount of multiples ofp_{1}*p_{2}. This is inclusion-exclusion, and in general, if the amount of elements is even, we add, otherwise, we subtract.slow) solution: Iterate over everyiin the range [1,N] and for everyi, factorize it, try out all combinations of primes and then, for every combination that results in a numberk, add if the amount of primes is even or subtract if the amount of primes is odd.k. A crucial observation is that the higher exponent of that numberkwill be 1, because we're trying combinations of different primes. Another crucial observation is that this numberkwill be seen times in total. Finally, each time we see it, it will contribute by to the final answer (or if the amount of primes is odd).O(N). We should precalculate the amount of prime factors of every number in the range [1, 10^{6}] (this can be done with a simple sieve), and we should cross out numbers that have some prime with an exponent higher than 1 (in other words, multiples of some square). Once we have precalculated all that, we simply iterate from 1 toNand for every numberxthat we didn't cross out, we add (or subtract) to our answer.N= 0, the answer is 1, exceptM= 0 too, in which case the answer is 0.Here's the simple C++ code: Ray Gun

Thanks, really appreciate your help.