Solved this problem finally after a couple of failed trials.

For whomever it may help:

• The answer for 2 1999999 is about 2*10^11. This is quite a big number, so O(n) where n is the answer will give you a time-out.
• Generating the Farey sequence until 1/A will be too slow, for this reason.
• One can use the Stern-Brocot tree to traverse all fractions between 1/(A+1) and 1/A. This is faster than generating the Farey sequence, in the sense that you skip all fractions smaller than 1/(A+1). However, it is still too slow (and might give you stack overflows when traversing with a DFS or out of memory when traversing with a BFS). The DFS implementation solved only 10 out of 13 test cases. I was not able to find a smart way to count the requested fractions in the Stern-Brocot sub-tree faster.
• Finally, after some research I found this paper: http://people.csail.mit.edu/mip/papers/farey/talk.pdf . Using the formulas and algorithm explained halfway through the paper, one can solve the problem with some DP in O(D log D).
• Obviously, don't use doubles when you can use integers. This changed one test case for me from Wrong Answer to Accepted.

Good luck!

PS "Easy" is not the right category for this problem if you ask me...