Я решил проблему, но не смог найти эффективное решение.
Постановка задачи:
При заданном дереве с N вершинами и N-1 ребра. Каждая вершина v обозначает значение, заданное C [v], где C [] - массив. Для этого дерева мы должны выполнить Q запросов, которые приведены ниже:
Запрос задается двумя целыми числами u, v. Определим значение A, которое задается произведением значений всех узлов, которые l ie на простом пути между u и v.
Более формально, если простой путь между u и v является [u, a, b ..., v], тогда
A = C [u] * C [a] * C [b] * ... * C [v] .
Для этого запроса нам нужно вывести число делителей A.
Ограничения: 1 <= <b>N, Q < = 100000, 1 <= <b>C [i] <= 1000000 для всех 1 <= <b>i <= N. </p>
Мой подход : Поскольку продукт может быть очень большим, я сохраняю основные факторы и его количество в качестве ответа.
Сначала я предварительно вычислил LCA для дерева, используя бинарный подъем. Затем я определил карту для каждого узла, в которой хранятся простые делители и их счетное произведение от root до текущего узла. Это может быть достигнуто простой DFS и отдельной функцией для объединения карт
(Примечание: я нахожу простую факторизацию узла с использованием sieve в O (LogN) * 1038 *)
Затем для каждого запроса типа [u, v] я нахожу LCA (скажем, L ). Теперь я вычитаю карту L из карты u (Примечание: карта L всегда будет подмножеством карты u) и аналогично для узла v.
Теперь у меня есть все простые множители и его количество произведений.
Теперь просто используя результат, что для числа K = a ^ p * b ^ q * c ^ r ..., число делителей D = (p + 1) * ( q + 1) * (r + 1) ... мы получаем ответ.
Анализ сложности времени:
Давайте определим M как число различных простых чисел до 1000000.
DFS будет работать за O (N * M) времени: для каждого узла при объединении карты наихудший случай будет, когда будут присутствовать все простые числа до М.
LCA предварительное вычисление: O (NLogN) время
предварительное вычисление сита: O (NLogLogN) время
Каждый запрос будет выполняться за O (M + LogN) время: O (LogN) для поиска LCA и O (M) для вычитания карты, чтобы найти главные факторы продукта.
So Сложность времени: O (NLogN + NM + NLogLogN + QMLogN) * 1066 *.
Теперь проблема что в худшем случае M порядка 50000. Таким образом, это увеличит сложность времени. Есть ли другой эффективный метод?
Ответ должен быть сообщен по модулю 1e9 + 7