Египетские дроби
Во времена Среднего царства Египта египтяне придумали новый способ записи дробей. Добавление определенного символа к иероглифу для целого числа означало обратное этого числа. Это позволяло легко записывать дроби вида 1 / n (называемые единичными дробями) — просто добавьте символ обратного числа к иероглифу для n.
Не существовало прямого способа представления дроби вида m / n, где m > 1. Вместо этого такие дроби записывались как сумма единичных дробей. Например, дробь 3 / 4 могла быть записана как:
Заметьте, что несколько сумм могут давать один и тот же результат; например, также можно записать как
Ваша задача — взять дробь и записать ее как сумму единичных дробей, используя "жадный" алгоритм. В жадном алгоритме вы последовательно вычитаете наибольшую возможную единичную дробь, пока не останется ноль. Например, для дроби жадный алгоритм найдет сумму за три шага следующим образом:
Обратите внимание, что на каждом шаге мы вычитали наибольшую возможную единичную дробь из оставшейся части нашей исходной дроби.
Необходимо добавить одно дополнительное ограничение, чтобы наши решения не становились слишком большими: каждый раз, когда мы вычитаем единичную дробь, мы должны оставаться с дробью, знаменатель которой строго меньше 1,000,000. Например, для дроби первые две единичные дроби, которые мы вычтем, будут и , оставляя нас с . В этот момент наибольшая единичная дробь, которую мы могли бы вычесть, будет , оставляя нас с
К сожалению, это оставляет нас с дробью, знаменатель которой больше 1,000,000, поэтому мы не можем использовать эту единичную дробь в нашей сумме. Мы переходим к следующей наибольшей единичной дроби, , которая оставляет нас с
Поскольку окончательный ответ сводится к дроби со знаменателем меньше 1,000,000, мы можем использовать эту единичную дробь, оставляя нас с окончательным ответом .
В этом случае нам пришлось пропустить только одну дробь. Однако в общем случае вам, возможно, придется пропустить много дробей, чтобы найти подходящую. Пока вы ищете, вам придется выполнять вычисления с многими дробями с большими знаменателями; убедитесь, что вы делаете это эффективно, иначе ваша программа может занять слишком много времени на выполнение.
Также убедитесь, что вы используете тип данных, достаточно большой, чтобы вместить большие числа, с которыми вы работаете. Несмотря на то, что мы ограничили знаменатели до 1,000,000, вам, возможно, придется вычислять промежуточные значения со знаменателями до 10^12. Для хранения таких значений потребуется 64-битное целое число (long в Java, long long в C/C++).
Наконец, стоит отметить, что по своей природе жадный алгоритм всегда найдет какой-то ответ, состоящий из дробей со знаменателями меньше 1,000,000, так как, по крайней мере, любая дробь может быть представлена как сумма единичных дробей с ее собственным знаменателем. Например:
Входные данные
Входные данные будут состоять из последовательности дробей; по одной на строку. Каждая строка будет содержать только два целых числа M и N, где 1 < M < N < 100, представляющих дробь . M и N не будут иметь общих делителей, больших 1. Конец входных данных будет обозначен двумя нулями: 0 0.
Выходные данные
Для каждой входной дроби вы должны вывести одну строку, содержащую числа D[1] ≤ D[2] ≤ D[3] ≤ … такие, что:
Это должна быть первая сумма, полученная с помощью жадного поиска при соблюдении ограничения на знаменатель в 1,000,000. Каждое число должно быть отделено одним пробелом, без начальных или конечных пробелов.