 # COPR16F: Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

HARD

### PREREQUISITES:

Euler Phi function, Prefix Sums, Farey’s Sequence, Recursion

### PROBLEM:

For query type “number”, find the number of of unique slopes from (0, 0) to (u, v) where u, v are integers and lie within triangle bounded by y=0, x=y and x=a, where a is specified in each test case.

For query type “find”, find the {k}^{th} slope in sorted sequence of unique slopes.

### EXPLANATION:

We will deal with query type “number” first. Let us see if we could derive the answer for x = a+1 line from x = a line. We see that (a + 2) integral points are more added in going from x = a to x = a+1. For all these points the slope from (0, 0) is given by - \frac{y}{x}. The number of different slopes among these (a+2) points which did not appear in the list for x = a will be given by phi(a+1), where phi(i), is the Euler phi function. To prove this, all the integral points with gcd(x, y) = 1 will have unique slope which is not available till x = a line. The number of such point is actually Euler phi function.

Thus answer for x = a+1 = (answer for x = a) + phi(a+1).

So, we can easily precompute all the Euler Phi values for 1 \leq n \leq {10}^{6}. Also, we should calculate the prefix sum for phi as well. Thus, for each query we can easily give the answer as Prefix_sum[a] in O(1) time.

Now, we will deal with query of type “find”. Note that we need to find the slope value in p/q form, not printing the answer in double. A little paper work will indicate that we actually need to find the {k}^{th} fraction in list of all fractions with denominator less than equal to a and numerator less than denominator with the condition that gcd(numerator, denominator) = 1. This problem is actually same as Farey sequences. For finding the {k}^{th} such number we can use the recurrence relations given by

{x}_{1} = 0, {y}_{1} = 1

{x}_{2} = 1, {y}_{1} = a

{x}_{r+2} = floor(\frac{{y}_{r} \ + \ a}{{y}_{r+1}}).{x}_{r+1} - {x}_{r}

{y}_{r+2} = floor(\frac{{x}_{r} \ + \ a}{{x}_{r+1}}).{y}_{r+1} - {y}_{r}

The above recurrence can be implemented in O(k) complexity easily using while loops.

### COMPLEXITY

O(n logn) for precomputing Euler Phi function

O(1) for query type number

O(k) for query type find

### AUTHOR’S SOLUTION:

Author’s solution can be found here.

1 Like