Решение задачи по программированию (желательно питон) Сложность O(квадрат(n))

Прохожу задачи яндекс алгоритмов 2018 для тренировки. Никак не могу понять задачу. Вот её содержание и решение. Помогите с кодом, не могу правильно его написать.

Содержание:


Алексей регулярно проводит собеседования с кандидатами на позицию стажёра. И хотя он провёл уже не одну сотню собеседований, в последнее время этот процесс даётся ему нелегко — кандидаты стали без труда решать все годами протестированные и отработанные задачи Алексея!


Делать нечего, и в преддверии очередного собеседования Алексей придумал новую задачу. Имеется числовая последовательность, на первом шаге состоящая из двух чисел 1. На каждом шаге следующем шаге между каждыми двумя соседними элементами добавляется новый элемент, равный их сумме. После первых нескольких шагов последовательность выглядит следующим образом:
1 1
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1


На собеседовании Алексей хочет попросить кандидата написать программу, которая по заданному числу $n$ будет определять, сколько раз число $n$ будет встречаться в последовательности на $n$-м шаге? Алексей ещё не научился решать свою задачу, но слышал, что кандидат, которого он будет сейчас собеседовать, добился высоких результатов в спортивном программировании, поэтому, скорее всего, легко справится с этим вопросом.

Решение:

Пусть мы имеем числа $pq$, стоящие рядом на некотором шаге и пусть $p>q$ (без ограничения общности). Тогда $p$ было получено как сумма $p-q$+$q$, то есть на предыдущем
шаге рядом стояли $p-q$ и $q$. Если $p-q < q$, то два шага назад справа от $q$ стояло число $2q-p$, если $p-q > q$, то слева от $p-q$ стояло число $p-2q$ и так далее. Так как $p$ и $q$
взаимно просты, то на каком-то шаге этот процесс, по сути являющийся разновидностью алгоритма Евклида, приведёт к тому, что с одной стороны окажется $1$, а с другой — некоторое
натуральное число. Но пара $(1,x)$ или $(x,1)$ для любого $x$ будет соседней последовательности на $x$-м шаге. А так как действия восстанавливаются однозначно,
то это значит, что и исходная пара $(p,q)$ в какой-то момент встретится в качестве соседней.


Таким образом, каждая упорядоченная пара взаимно простых чисел ровно один раз встречается в качестве соседей в заданной последовательности. Поэтому задача сводится к подсчёту количества упорядоченных пар взаимно простых чисел, дающих в сумме $n$. Так как если $p$ и $n$ взаимно просты, то и $p$ и $n-p$ взаимно просты, то количество таких пар можно поставить в однозначное соответствие количеству чисел, взаимно простых с $n$, или значению функции Эйлера от $n$.


Подсчёт же количества таких чисел является известной задачей и опирается на мультипликативность функции Эйлера: если $n=p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_n^{k_n}$, то взаимно простых с $n$
чисел будет $(p_1^{k_1}-p_1^{k_1-1}) \cdot (p_2^{k_2}-p_2^{k_2-1}) \cdot \ldots (p_n^{k_n}-p_n^{k_n-1})$. Раскладываем $n$ на простые множители за время