Это очень интересный вопрос, и мне очень понравилось думать об этом, и я не знаю, почему он получил так много отрицательных голосов. В любом случае, ниже мой грубый набросок решения. Я обновлю свой ответ позже, если добавлю к нему некоторые уточнения.
Как подсказывает @ user3357359 answer , нам нужен более эффективный способ генерации взаимных кодов. Обычный метод (который используется в решателях диофантовых уравнений): Последовательность Фарея .
Определение: Последовательность Фарея порядка n между a/b и c/d - восходящая (по значению) последовательность неприводимых дробей p/q, такая, что a/b <= p/q <= c/d, где q < n.
Свойства последовательности Фари представлены в this бумага . Итак, у нас есть несколько вопросов под рукой:
Как эффективно сгенерировать Последовательность Фарея порядка n?
Знание первого элемента a0/b0 = a/b и второй элемент a1/b1, можно сгенерировать a2/b2, используя следующий алгоритм (со сложностью O(1)):
k = int((n + b0) / b1)
a2 = k * a1 - a0
b2 = k * b1 - b0
Как получить второй элемент Последовательность Фарея порядка n?
Мы знаем, что знаменатель находится где-то в диапазоне 1..n. Мы также знаем, что a/b и c/d являются соседями в Farey Sequence тогда и только тогда, когда b*c - a*d = 1. Таким образом, вычисляя значение от d до 1..n, мы можем найти наименьшую дробь, которая будет следующей в последовательности. Сложность O(n).
Как мы решаем, какой порядок последовательности Фарея мы должны сгенерировать?
Слепое порождение порядка N, когда N по величине 10^18 глупо. Более того, вам не хватит памяти для этого. Нам нужно только сгенерировать Последовательность Фэри некоторого порядка k, чтобы длина его была больше, чем n, который ограничен 200000. Это самая сложная часть этого алгоритма, и сейчас инструменты в теории чисел позволяют нам только оценить: |F_k| = 3*k^2 / pi^2. Итак, у нас есть:
k = ceil(sqrt(n * pi^2)) + C
На стр. 11 этой статьи вы также можете найти ошибку аппроксимации этой формулы, так что вы получите больше места для ошибки, таким образом, C , Обратите внимание, что для каждого a/b и c/d длина F_k будет разной.
Подводя итог, псевдокод для алгоритма:
1. Estimate the order k of the Farey Sequence to generate, such that |F_k| >= n
2. Calculate the second element of F_k. O(k), where k << n and 1 < n < 200000
3. Generate the whole Farey Sequence. O(n), where 1 < n < 200000
4. Sort by the requirements. O(n log n), where 1 < n < 200000
В худшем случае, когда ваша оценка в step 1 дала меньше элементов, чем n, вам нужно будет сгенерировать снова, используя чуть более высокий порядок k'. Что только увеличит время выполнения вашего алгоритма на постоянную. Таким образом, общая сложность составляет в среднем O(n log n), где n < 200000.
Замечания: узким местом этого алгоритма является оценка порядка k. Этого можно полностью избежать, используя не Последовательность Фаре, а * Stern-Brocot Tree . Дерево генерируется именно в том порядке, в котором вы нуждаетесь, но я сомневаюсь, что в произвольной настройке с a/b != 0/1 и c/d != 1/1 оно будет перебирать все дроби в хорошем порядке.