Количество делителей произведения двух взаимно простых чисел равно произведению количеств их делителей. Иными словами, если обозначить за $$$F(x)$$$  — количество делителей числа $$$x$$$, то $$$F(x \cdot y) = F(x) \cdot F(y)$$$, если $$$x, y$$$ взаимно просты. Потому что каждый делитель их произведения уникально образуется комбинацией делителей первого и второго чисел, а отсутствие общих множителей гарантирует, что каждая комбинация дает новый делитель.

Найти количество делителей числа x можно за $$$O(\sqrt{x})$$$.

Итоговая асимптотика: $$$O(\sqrt{x} + \sqrt{y})$$$