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.