### isat1729's blog

By isat1729, history, 6 years ago,

Problem Name: Ray Gun

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

Any hints for the solution will be really appreciated.

• +16

 » 6 years ago, # |   +4 There are many observations to make in order to get to a working solution. For every lattice point (i, j), the ray that intersects it is unique and it's identified by the pair , where g is the gcd of i and j. The problem is now reduced to counting the number of irreducible fractions such that a ≤ N and b ≤ M. This is the same as counting for every i between 1 and N, the amount of numbers in the range [1, M] that are coprime with i. Consider a certain number x with prime factors p1, p2. 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 of p1 minus the amount of multiples of p2 plus the amount of multiples of p1 * p2. This is inclusion-exclusion, and in general, if the amount of elements is even, we add, otherwise, we subtract. So now we have a working (but slow) solution: Iterate over every i in the range [1, N] and for every i, factorize it, try out all combinations of primes and then, for every combination that results in a number k, add if the amount of primes is even or subtract if the amount of primes is odd. The previous approach is very slow for two reasons: You'll be factorizing each number every time and you'll be doing a lot of repeated work. Every combination of primes you try out at each step will result in a certain number k. A crucial observation is that the higher exponent of that number k will be 1, because we're trying combinations of different primes. Another crucial observation is that this number k will 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). Knowing all this, we can precalculate a lot of stuff and then solve each test case in O(N). We should precalculate the amount of prime factors of every number in the range [1, 106] (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 to N and for every number x that we didn't cross out, we add (or subtract) to our answer. Final observations: We should add 2 to our answer (the two borders). If N = 0, the answer is 1, except M = 0 too, in which case the answer is 0. Here's the simple C++ code: Ray Gun
•  » » 6 years ago, # ^ |   +5 Thanks, really appreciate your help.