Дружелюбные пауки

Заметим, что если строить граф по определению, то он выйдет большим. Это будет надвигать нас на мысль, чтобы его сделать более компактным. Давайте создадим двудольный граф, левая доля которого — все вершины из условия, а в правой доле каждая вершина будет отвечать за какое-то простое число, не большее, чем максимальное число из левой доли. Проведем ребро из вершины левой доли 𝑣
 в вершину правой доли 𝑢
 в случае, если 𝑎𝑣
 делится нацело на простое число, соответствующее вершине 𝑢
. В данном графе от вершины 𝑠
 до вершины 𝑡
 запустим bfs и выведем расстояние, деленное на 2
.

Теперь о том, как быстро построить такой граф. Очевидно, что у числа 𝑎𝑖
 будет не более log𝑎𝑖
 различных простых делителей. Тогда давайте факторизуем 𝑎𝑣
 и проведем ребра от вершины 𝑣
 до каждого простого в факторизации.