\begin{tutorial}{Greatest Common Divisor}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Геннадий Короткевич\\
         Разработка: & Геннадий Короткевич\\
     \end{tabular}
}

Написав простое решение, перебирающее все пары, и примерно оценив рост числа подходящих пар в зависимости от $n$, можно понять, что для $n \le 2 \cdot 10^5$ хватит времени и памяти выписать все подходящие пары в один массив. Действительно, для $n = 2 \cdot 10^5$ таких пар $4\,480\,708$.

Заметим, что после первой итерации алгоритма пара $(x, y)$ заменится на пару $(y, w)$, где $w = x$ \t{div}~$y$. При этом произведение элементов в новой паре $y \cdot w$ не превышает $x$, который в свою очередь не превышает $n$, а значит, возможных пар $(y, w)$ после первой итерации алгоритма всего $O(n \log n)$, и их все можно перебрать.

Зафиксируем некоторую такую пару вида $(y, w)$. Запустим алгоритм из условия до конца, пусть он вернёт некоторое число $g$. Если $y$ не делится на $g$, такая пара нам неинтересна. Иначе нам интересны все такие значения $x$, что $x$ \t{div} $y = w$ и $\operatorname{gcd}(x, y) = g$. Первое условие эквивалентно неравенствам $y \cdot w \le x < y \cdot (w + 1)$, а из второго условия следует, что $x$ должно делиться на $g$. Значит, переберём все делящиеся на $g$ числа $x$ из диапазона $[y \cdot w; y \cdot (w + 1))$ и для каждого из них проверим условие $\operatorname{gcd}(x, y) = g$. Таким образом мы и найдём все подходящие пары $(x, y)$.

\end{tutorial}
