Вот сочинил задачку по информатике (олимпиадную) . Попробуйте!

Question

Надеюсь, вы знаете алгоритм Евклида нахождения НОД.

Задача: для заданного N указать пару чисел a N, b N, чтобы алгоритм Евклида НОД (а, b) потребовал максимального числа шагов.

Например, для N=3*10^9 можно найти такую пару чисел, что процесс потребует 48 шагов.

Answer 1

Первое, что приходит в голову - найти НОД для всех пар чисел (a, b) N, для каждого нахождения записать количество шагов, а так же пары чисел в массивы, после чего найти в массиве количества шагов максимальное значение и по номеру элемента отобразить эту пару чисел.

Впрочем можно упростить алгоритм, просто записывая в одну переменную количество шагов, в другую пару чисел, и обновлять эти переменные, если количество шагов в новой итерации нахождения НОД будет выше, чем в переменной. Но тогда не получится отобразить все пары чисел, для которых количество шагов максимально, если их больше одной.