Пусть E(x₀, y₀) будет числом шагов, необходимых для определения наибольшего общего делителя чисел x₀ и y₀, используя алгоритм Евклида. Более формально:
x₁ = y₀, y₁ = x₀ mod y₀
x_n = y_n-1, y_n = x_n-1 mod y_n-1
E(x₀, y₀) - это наименьшее n такое, что y_n = 0.

Получаем E(1,1) = 1, E(10,6) = 3 и E(6,10) = 4.

Определим S(N) как сумму E(x,y) для 1 ≤ x,y ≤ N.
Имеем S(1) = 1, S(10) = 221 и S(100) = 39826.

Найдите S(5·10⁶).