see tutorial about stern-brocot's tree Tutorial. this is infinity binary tree which nodes are irreducible fractions. enumerate nodes of tree using BFS. it is given one number n and one fraction . Your task is to determine what fraction is written on the node LCA(n, ) where LCA is Lowest Common Ancestor of nodes n and . (in first case node is defined by its number and in second case node is defined by fraction). 0 < a, b < 10⁹ and 0 < n < 10¹⁸.

what is efficient method for finding what fraction is written on the node by its fraction and vice versa?