Stern–Brocot tree
Difference between en1 and en2, changed 184 character(s)
see tutorial about stern-brocot's tree [Tutorial](https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree). 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 $\frac{a}{b}$. Your task is to determine what fraction is written on the node LCA($n$, $\frac{a}{b}$) where LCA is Lowest Common Ancestor of nodes n and $\frac{a}{b}$. (in first case node is defined by its number and in second case node is defined by fraction). $0<a,b<10^9$ and $0<n<10^18$. ↵
![see example of tree](/predownloaded/81/e0/81e0bba6d68cfd2e498d3de491c2ae0aada6aabc.png)↵
what is efficient method for finding what fraction is written on the node by its fraction and vice versa?↵
↵
↵
![see example of tree](/predownloaded/81/e0/81e0bba6d68cfd2e498d3de491c2ae0aada6aabc.png)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Butskhrikidze 2019-02-27 12:29:16 184
en1 English Butskhrikidze 2019-02-27 12:28:48 760 Initial revision (published)