### PROBLEM LINK:

**Author:** Bhuvnesh Jain

**Tester:** Bhuvnesh Jain

**Editorialist:** Bhuvnesh Jain

### DIFFICULTY:

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.