Дерево рациональных чисел

Бесконечное полное двоичное дерево устроено так: корень — 1/1, а у вершины p/q левый потомок — p/(p+q), правый — (p+q)/q. Обход по уровням слева направо даёт последовательность 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, …; каждое положительное рациональное число встречается в ней ровно один раз. Номера позиций начинаются с 1.

Функция получает kind, a и b:

• при kind = 1 верните [p, q] — числитель и знаменатель элемента на позиции a (1 ≤ a < 2^53); b равно 0;
• при kind = 2 верните [n] — позицию дроби a/b, где a и b взаимно просты, а позиция меньше 2^53.

Пример: 1, 5, 0 → [3, 2]; 2, 3, 2 → [5].

Источник: Coding Competitions Archive, kickstart/2013/round_a/rational_number_tree · © Google LLC · Apache-2.0 · условие переведено и дополнено